[BOJ] (DP) 15990번 1, 2, 3 더하기 5

다이나믹 프로그래밍을 이용하는 문제.

 

여기서 중요한 것은, 수가 굉장히 커진다는 것인데, 

 

a+b+c = d 일때, 모든 k에 대하여

{(a%k) + (b%k) + (c%k)} % k = d % k 가 성립한다.

 

dp = [[0] for _ in range(100001)]
dp[1] = [1, (1, 0, 0)]
dp[2] = [1, (0, 1, 0)]
dp[3] = [3, (1, 1, 1)]
for i in range(4, 100001):
    a = dp[i-3][1][0] + dp[i-3][1][1]
    b = dp[i-2][1][0] + dp[i-2][1][2]
    c = dp[i-1][1][1] + dp[i-1][1][2]

    dp[i] = [a%1000000009 + b%1000000009 + c%1000000009, (c%1000000009, b%1000000009, a%1000000009)]

for _ in range(int(input())):
    n = int(input())
    
    print(dp[n][0] % 1000000009)

 

 

 

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

15990번: 1, 2, 3 더하기 5