1437 수 분해

Link

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

Detail

딱봐도 DP임 수 a의 분해곱의 최댓값을 $F(a)$ 라고 한다면

• a를 두 수 i, j로 나눈다.
• $F(i)+F(j)$ 중 최대값이 a가 된다. (O(a))
• a가 100만까지라는데 되냐 이거?

뭔 DP 여 ㅋㅋㅋㅋ

그냥 곱할 수 있는 수를 최대한으로 늘리는 것이 이득 이때 2가 세개인것보다 3이 2개인게 미세하게 크기때문에 (8, 9) 숫자 안에서 3을 최대한 꺼낸 다음에 남아도는 2를 곱해주면 끝.

이 때 3 + 1보다 2 + 2 로 분해하는 것이 이득이기 때문에 n % 3 == 1일경우 2를 두개로 상정하고

싹 곱해주면 결과를 알 수 있다.

Code

#include <bits/stdc++.h>
#define MOD 10007
#define MAX 1'000'000
 
using namespace std;
typedef long long ll;
  
int solve(int n) {
    if(n <= 2) return n;
 
    int threeCnt = n / 3;
    int twoCnt = 0;
 
    if (n % 3 == 1) {
        threeCnt--;
        twoCnt = 2;
    } else if (n % 3 == 2) {
        twoCnt = 1;
    }
 
    int answer = 1;
    for (int i = 0; i < threeCnt; i++) {
        answer *= 3;
        answer %= MOD;
    }
 
    for (int i = 0; i < twoCnt; i++) {
        answer *= 2;
        answer %= MOD;
    }
 
    return answer;
 
}
 
int main() {
    int n; cin >> n;
 
    cout << solve(n);
    return 0;
}