[BOJ] 15988번 1, 2, 3 더하기 3

dp[1] = 1
dp[2] = 2
dp[3] = 4

 

dp[4]:

  dp[1]에 3이 더해진 경우

  dp[2]에 2가 더해진 경우

  dp[3]에 1이 더해진 경우

따라서 dp[4] = dp[1] + dp[2] + dp[3]

 

이를 일반화 하면, dp[n] = dp[n-3] + dp[n-2] + dp[n-1]   (if n ≥ 4)

 

dp = [0] * (1000001)
dp[1] = 1
dp[2] = 2
dp[3] = 4

for _ in range(int(input())):
    n = int(input())

    if n<4:
        print(dp[n])
        continue
        
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        dp[i] %= 1000000009
        
    print(dp[n])