BOJ 1353 합과 곱

문제 링크입니다.

관찰

음이 아닌 실수들의 합과 곱이 주어졌을 때, 필요한 실수 개수의 최솟값을 구해야 합니다.

합과 곱이 같은 경우의 답은 자명하게 1입니다.

절대부등식 활용하기

산술-기하 평균 부등식에 의해, 답이 N이라면 N 이상의 모든 정수 n에 대해 $({\Sigma \over n})^n \ge \Pi$가 성립합니다.

역으로 $({\Sigma \over n})^n \ge \Pi$가 성립한다면, $({\Sigma A \over n})^n = \Pi$인 길이 n의 수열 A가 존재합니다. 이때 이 수열 A의 한 원소에 적당한 값을 곱하고 다른 원소에 그 역수를 곱해주는 것으로 원소들의 곱은 유지하면서 합을 원하는 만큼 늘릴 수 있습니다.

따라서 답은 $({\Sigma \over n})^n \ge \Pi$를 만족하는 n의 최솟값입니다.

답의 상한 구하기

$\Pi$는 고정된 상수니 $({\Sigma \over n})^n$ 쪽에 집중합시다. 고정된 $\Sigma$에 대해 이 값의 최댓값은 $n = {\Sigma \over e}$일 때임을 $({\Sigma \over n})^n$를 n에 대해 미분하면 알 수 있습니다.

이 값을 상한으로 잡고 n에 대한 이분 탐색을 돌면 답을 구할 수 있습니다.

이와 별개로 $\Pi \le 1e9$ 라는 조건을 생각해 보았을 때 실제로 나올 수 있는 답이 크지 않습니다. 굳이 극댓값까지 가보지 않아도, $\Sigma$가 한 60 정도를 넘어가면 값의 증가 속도가 엄청 빨라서 1e9을 뚫어버립니다. 대강 20을 조금 넘는 값이 가능한 답의 최댓값인데, 이 정도면 이분 탐색과 퍼포먼스 차이가 크게 나지 않습니다.

그래서 그냥 n = 1부터 증가시키면서 나이브하게 확인해주면 문제를 해결할 수 있습니다.

코드

#include<iostream>
#include<cmath>
using namespace std;

int main(){
	int hap, gop, x = 1;
	double old = 0;
	cin >> hap >> gop;
	if(hap==gop){
		cout << 1;
		return 0;
	}
	while(++x){
		double t = pow(1.0*hap/x, x);
		if(t >= gop){
			cout << x; return 0;
		}
		else if(t < old){
			cout << -1; return 0;
		}
		old = t;
	}
}