문제

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

나의 코드

from sys import stdin
input = stdin.readline

t = int(input())

dp = [ [0] * 4 for _ in range(100000+1) ]
dp[1] = [0, 1, 0, 0] # n이 1일때 1로 끝나는 수 1개
dp[2] = [0, 0, 1, 0] # n이 2일때 2로 끝나는 수 1개
dp[3] = [0, 1, 1, 1] # n이 3일때 1, 2, 3으로 끝나는 수 1개씩 있음.

for i in range(4, 100000+1):

    # 만약 i가 6이라면 연속된 숫자의 합으로는 쓰지 말라고 했으니

    dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1000000009 # 5에서 2로 끝나는 수에 +1, 5에서 3으로 끝나는 수에 +1
    dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1000000009 # 4에서 1로 끝나는 수에 +2, 4에서 3으로 끝나는 수에 +2
    dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1000000009 # 3에서 1로 끝나는 수에 +3, 3에서 2으로 끝나는 수에 +3

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

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

    

느낀점

1차원 DP만 생각하다가 시간 날림
2차원으로 생각할 줄 알아야 한다.