[백준_15990] 1, 2, 3 더하기 5 python

규칙은 쉽게 찾았다.

dp라는것을 아는데 시간이 걸렸을 뿐

dp가 너무싫다

오늘의 교훈. dp는 한번만 만드는거다.

import sys

input = sys.stdin.readline

 

　dp = [0] * 100001

for i in range(100001):

　dp[i] = [0,0,0]

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

t = int(input())

for _ in range(t):

　n = int(input())

　print(sum(dp[n]) % 1000000009)