BOJ 1437 - 수 분해

문제

BOJ 1437 - 수 분해

자연수 N을 여러 양의 정수의 합으로 나타낼 때, 그 수들의 곱이 최대가 되는 값을 10007로 나눈 나머지를 구하라.

입력

자연수 N이 주어진다 (1 이상 100만 이하).

출력

곱의 최댓값을 10007로 나눈 나머지를 출력한다.

예제

풀이

수학적으로 곱을 최대화하려면 가능한 한 3으로 분해하는 것이 최적이다. N을 3으로 나눈 나머지에 따라 분기 처리한다.

1. N이 4 이하이면 그 자체를 출력한다 (분해하면 오히려 감소)
2. N % 3 == 0이면 3^(N/3)을 출력한다
3. N % 3 == 1이면 3 하나를 빼고 4를 곱한다: 3^((N-4)/3) * 4
4. N % 3 == 2이면 2 하나를 추가한다: 3^((N-2)/3) * 2
5. Python의 pow(base, exp, mod)로 모듈러 거듭제곱을 O(log N)에 수행한다

핵심 아이디어: AM-GM 부등식에 의해 합이 고정일 때 같은 수로 분해해야 곱이 최대이며, 미분으로 최적 분해 단위가 e(≈2.718)에 가까운 3임을 알 수 있다.

코드

N = int(input())
M = 10007
if N < 5:
    print(N)
elif N % 3 == 0:
    print(pow(3, N // 3, M))
elif N % 3 == 1:
    print((pow(3, (N - 4) // 3, M) * 4) % M)
else:
    print((pow(3, (N - 2) // 3, M) * 2) % M)

복잡도

• 시간: O(log N)
• 공간: O(1)