[백준] 15990번 1,2,3 더하기 5

import sys
input = sys.stdin.readline

t = int(input())

dp = [[0 for _ in range(3)] for _ in range(100001)]

dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]

for i in range(4, 100001):
    
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % 1000000009
    dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) % 1000000009
    dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) % 1000000009

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

 

풀기 어려운 문제다. 이걸 어떻게 풀지? 한참 연습해야할 것 같다

1,2,3 더하기가 단순한 점화식 문제였다면, 이번 문제는 이중 배열을 사용해야하는 다소 복잡한 문제다

 

포인트는

 

i가 6일 경우 

5 + 1 = 4 + 2 = 3 + 3 = 6이므로

5가 2와 3으로 끝나는 경우에서 1을 더해주고

4가 1과 3으로 끝나는 경우에서 2를 더해주고

3이 1과 2로 끝나는 경우에서 3을 더해주면 6을 만들 수 있으므로

 

해당 규칙을 통해 점화식을 만들어주는 것이다.

 

다시 풀라해도 못풀겠다