나의 코드
import sys
input = sys.stdin.readline
T=int(input())
dp=[[],[1,0,0],[0,1,0],[1,1,1]]
last=4
for _ in range(T):
n=int(input())
if len(dp)-1>=n:
print(sum(dp[n])%1000000009)
continue
for i in range(last,n+1):
tmp=[0,0,0]
tmp[0]=(dp[i-1][1]+dp[i-1][2])%1000000009
tmp[1]=(dp[i-2][0]+dp[i-2][2])%1000000009
tmp[2]=(dp[i-3][0]+dp[i-3][1])%1000000009
dp.append(tmp)
last=n+1
print(sum(dp[n])%1000000009)수행시간: 224ms
풀이
dp[i]는 정수i를 1,2,3들의 합으로 만들때 맨끝이 1,2,3인 경수의 개수를 저장하는 리스트이다. 예를 들어 정수4는 1+2+1, 1+3, 3+1로 1로 끝나는 경우 2개, 2로 끝나는 경우 0개, 3으로 끝나는 경우 1개만들수있다. 따라서 dp[4]는 [2,0,1]의 값을 가진다.
1로 끝나는 경우: dp[i-1]의 끝이 2,3으로 끝나는 경우의 합이다.
2로 끝나는 경우: dp[i-2]의 끝이 1,3으로 끝나는 경우의 합이다.
3로 끝나는 경우: dp[i-3]의 끝이 1,2로 끝나는 경우의 합이다.
- %1000000009를 각 경우에 안해주면 시간초과가 발생한다.
