[백준-15988] 1,2,3 더하기 3

---

나의 코드

import sys
input = sys.stdin.readline

T=int(input())
dp=[1,1,2,4]
last=4
for _ in range(T):
    n=int(input())
    if n<last:
        print(dp[n])
        continue
    for i in range(last,n+1):
        dp.append((dp[i-3]+dp[i-2]+dp[i-1])%1000000009)
    last=n+1
    print(dp[n])

수행시간: 544ms

---

풀이

n은 (n-3을 만드는 구성)+3 , (n-2를 만드는 구성)+2, (n-1을 만드는 구성)+1으로 만들수 있다.
따라서 dp[n]=dp[n-3]+dp[n-2]+dp[n-1] 이다.