백준 ) 1,2,3더하기5 (미완)

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력 1

3
4
7
10

예제 출력 1

3
9
27

풀이

1,2,3더하기 문제 점화식은
D[N] = D[N-1] + D[N-2] + D[N-3] (N을 만드는 방법의 수)

'같은 수를 두 번 이상 연속해서 사용하면 안 된다.'
연속하게 사용하지 않을려면 무엇으로 끝났는지 알아야한다.

마지막에 사용한 수 j 를 추가
D[i][j]=i를1,2,3의 합으로 나타내는 방법의수, 마지막에 사용한 수는j

+1 = i -> D[i][1] = D[i-1][2] + D[i-1][3]
+2 = i -> D[i][2] = D[i-1][1] + D[i-1][3]
+3 = i -> D[i][3] = D[i-1][1] + D[i-1][2]

-> D[i][1]+D[i][2]+D[i][3] 이 정답