[파이썬] [DP] 백준 15988 1, 2, 3 더하기 3

문제

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

15988번: 1, 2, 3 더하기 3

코드

t=int(input())

#dp배열을 n의 방법의 수를 저장하는 것으로 사용
dp=[0]*1000001
dp[1]=1
dp[2]=2
dp[3]=4
# 예를 들어 n이 4인경우, dp[1]에서 3을 추가하는 경우, dp[2]에 2를 추가하는 경우, dp[3]에 1을 추가하는 경우만 존재
for i in range(4,1000001):
    dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000009

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