boj 1437 수 분해

https://www.acmicpc.net/problem/1437

 

숫자 N을 0이 아닌 정수의 합으로 나타낼 수 있으며, 그 수들의 곱의 최댓값을 구하는 문제입니다.

우선 그 합을 이루는 정수는 N이 커질수록 답이 커질수밖에 없습니다.

그 기준은 5가 되겠습니다.

5 = 2 + 3이며, 2 * 3 = 6 > 5이기 때문이죠.

5보다 작은 수는 그 수 자체를 곱하는게 더 크다고 할 수 있습니다.

 

그렇다면 문제를 쉽게 해결할 수 있습니다.

N을 5보다 작은 어떤 수로 계속 빼면 답을 구할 수 있습니다.

그 수는 3이나 4가 될 수 있을텐데, 6 = 2 + 2 + 2 = 3 + 3의 경우를 보시면 3이 최대한 많이 들어가는 수가 크다는 것을 알 수 있습니다.

다른 수로 직접 구해보셔도 4보다는 3으로 나누는 것이 제일 이득입니다.

따라서 N < 5가 되기 전까지는 3을 계속 빼주도록 하고, 남은 5 미만의 N을 곱해주시면 됩니다.

 

 

#include <iostream>
#define MOD 10007
using namespace std;
 
int N;
 
void func() {
    int ret = 1;
    while (N >= 5) {
        N -= 3;
        ret = (ret * 3) % MOD;
    }
    cout << (ret * N) % MOD << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}