[백준 문제풀이] 15990번 : 1,2,3 더하기 5

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

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

💡 생각보다 규칙 찾는게 어려웠다. 점화식은 나오지 않는 문제

1. 소스코드

T=int(input())
dp = [[0]*4 for ㅑ in range(100001)]

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

for i in range(4,100001):
    for j in range(1,4):
        dp[i][j]=sum(dp[i-j])%1000000009 -dp[i-j][j]
for i in range(T):
    n=int(input())
    print(sum(dp[n])%1000000009)