BOJ 1353. 합과 곱

문제 링크

 

문제 풀이

 이 문제는 어떤 양의 실수$\leq 10^9$들의 합에 대한 정보와 곱에 대한 정보가 주어질 때 이 수들의 개수로 가능한 최솟값을 출력하는 문제이다.

 합과 곱이 주어졌으므로 산술기하 평균 부등식 AM-GM inequality 을 떠올릴 수 있다. 이 실수들의 합, 곱, 개수를 각각 $S, P, N$이라 할 때 다음이 성립한다.

$$S \leq N\sqrt[N]{P}$$

$$\Rightarrow P \leq (\frac{S}{N})^N$$

 

 따라서 이를 만족하는 $N$의 최솟값을 찾으면 된다. 이때 불가능한 경우를 따지기 위해 $f(N) = (\frac{S}{N})^N$로 두고 미분하여 최댓값을 찾아야한다.

$$(\ln_{}{f(N)})^{\prime}=\frac{f^{\prime}(N)}{f(N)} = (Nln\frac{S}{N})^{\prime} = ln(\frac{S}{N\times e}) $$

여기서 $N = \frac{S}{e}$일 때 $f^{\prime}(N) = 0$으로 극대가 된다. 따라서 이 경우에 대해서 $P$보다 큰지 작은지 먼저 따져주어야한다.

 

 

코드  

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->ios::sync_with_stdio(0);
const long double e = 2.7182818459045;

int S,P;

void input(){
    cin>>S>>P;
}

int solve(){
    if(S == P) return cout<<1, 0;
    if(pow(e,S/e) < P) return cout<<-1,0;
    
    long double prv;
    for (int i = 2; ; i++) {
		long double cur = pow((long double) S / i, i);
		if (prv > cur) return cout << -1 << '\n',0;
		if (cur >= P) return cout << i << '\n',0;
		prv = cur;
	}
}

int main() {
    fastio;
    
    input();
    solve();
}