처음에 몰라서 답을 보았다...
아마 점화식을 보면 이해가 안될 것 이다.
마지막에 1, 2, 3으로 끝나게 되는데
[1로 끝나는 갯수, 2로 끝나는 갯수, 3으로 끝나는 갯수][0,1,2]
1로 끝나면 뒤에 2, 3을 붙일 수 있다. 뒤에 1을 붙이려면 구하려는 수보다 1 작은 수 에서 붙여야한다.
dp[i][0] = dp[i - 1][1] + dp[i - 1][2]
2로 끝나면 뒤에 1, 3을 붙일 수 있다. 뒤에 2를 붙이려면 구하려는 수보다 2 작은 수에 붙여야한다.
dp[i][1] = dp[i - 2][0] + dp[i - 2][2]
3으로 끝나면 뒤에 1, 2를 붙일 수 있다. 뒤에 3을 붙이려면 구하려는 수보다 3 작은 수에 붙여야 한다.
dp[i][2] = dp[i - 3][0] + dp[i - 3][1]
해당 리스트를 더해서 나눠 출력하면 정답이 된다.
a = list(int(input()) for _ in range(int(input())))
dp = list([0, 0, 0] for _ in range(max(a) + 1))
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]
for i in range(4, max(a) + 1):
dp[i][0] = dp[i - 1][1] % 1000000009 + dp[i - 1][2] % 1000000009
dp[i][1] = dp[i - 2][0] % 1000000009 + dp[i - 2][2] % 1000000009
dp[i][2] = dp[i - 3][0] % 1000000009 + dp[i - 3][1] % 1000000009
for i in a:
print(sum(dp[i]) % 1000000009)
smilegate