[백준] 1437 - 수 분해

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

1437번: 수 분해

 

이 문제를 처음 보고 당연히 2로 계속 분해하면 곱의 개수가 많아지고, 분해 곱이 커질 줄 알았다.

하지만 그렇지 않고, 3으로 분해했을 때가 가장 컸다.

 

다음과 같은 경우를 보자.

10 = 2 + 2 + 2 + 2 + 2 -> 2 * 2 * 2 * 2 * 2 = 32

10 = 3 + 3 + 2 * 2 -> 3 * 3 * 2 * 2 = 36

 

또한, 5 이상의 모든 수는 2와 3의 합으로 나타낼 수 있다.

주의해야 할 점은, 4의 최대 분해 곱은 4라는 것이다. (2 + 2 또는 4)

 

#include <iostream>
using namespace std;

int main() {
	
    int n;
    cin >> n;
    long long ans = 1;
    while (n >= 5) {
    	ans = (ans * 3) % 10007;
        n -= 3;
    }
    
    ans = (ans * n) % 10007;
    cout << ans;
}