kingsubin

import java.util.*;

public class boj_15990 {
    static final long mod = 1000000009L;
    static final int limit = 100000;
    static long[][] d = new long[limit+1][4];
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        for (int i=1; i<=limit; i++) {
            if (i-1 >= 0) {
                d[i][1] = d[i-1][2] + d[i-1][3];
                if (i == 1) {
                    d[i][1] = 1;
                }
            }
            if (i-2 >= 0) {
                d[i][2] = d[i-2][1] + d[i-2][3];
                if (i == 2) {
                    d[i][2] = 1;
                }
            }
            if (i-3 >= 0) {
                d[i][3] = d[i-3][1] + d[i-3][2];
                if (i == 3) {
                    d[i][3] = 1;
                }
            }
            d[i][1] %= mod;
            d[i][2] %= mod;
            d[i][3] %= mod;
        }
        
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println((d[n][1] + d[n][2] + d[n][3])%mod);
        }
    }
}

- 생각이 안난다 ....

- 머리가 굳은거같다 ....

 

- 합의 마지막에 올 수 있는 수는 1, 2, 3이 있다.

- 마지막에 1 올 경우 그 앞은 2, 3 -> dp[i][1] = dp[i-1][2] + dp[i-1][3];

- 마지막에 2 올 경우 그 앞은 1, 3 -> dp[i][2] = dp[i-2][1] + dp[i-2][3];

- 마지막에 3 올 경우 그 앞은 2, 3 -> dp[i][3] = dp[i-3][2] + dp[i-3][3];

 

- 이중배열로 dp를 담는다.