회고

1437번 문제를 dp로 풀었다.

---

문제 풀이

dp[n] = n의 분해곱 최댓값

dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 4 => 2+2
dp[5] = 6 => 2+3
dp[6] = 9 => 3+3
dp[7] = 12 => 2+2+3
dp[8] = 18 => 2+3+3
dp[9] = 27 => 3+3+3

dp[n] = dp[n-3]*3

코드

import sys
input = sys.stdin.readline

n = int(input())
dp =  [0]*100001
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 4

for i in range(5, n+1):
    dp[i] = (dp[i-3]*3)%10007
print(dp[n])