백준 15990 1, 2, 3 더하기 5

mod = 1000000009
d = [[0] * 3 for _ in range(100001)]
d[0] = [1, 0, 0]
d[1] = [1, 0, 0]
d[2] = [0, 1, 0]
for i in range(3, 100001):
    d[i][0] += (d[i-1][1] + d[i-1][2]) % mod
    d[i][1] += (d[i-2][0] + d[i-2][2]) % mod
    d[i][2] += (d[i-3][0] + d[i-3][1]) % mod
d[0] = [0, 0, 0]
t = int(input())        
for _ in range(t):
    n = int(input()) 
    print(sum(d[n]) % mod)

1. dp + 이차원배열
2. n = 0, 1, 2 일 때 예외처리
3. d의 열이 3개밖에 안되는데 반복문으로 해결하려고 해서 시간 초과만 남
   -> 단순하게 생각