[전체 코드]

// 1, 2, 3 더하기 5
package DynamicProgramming;
import java.util.Scanner;

public class BJ15990 {  
    static int t, maxCase = 0, MOD = 1000000009;
    static long[][] dp; 
    static int[] cases;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        cases = new int[t];

        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            cases[i] = n;
            if (maxCase < n) {
                maxCase = n;
            }
        } 
        // 테스트 케이스 중에서 가장 큰 값을 기준으로 dp 구성 (1번만 호출)
        buildDP(maxCase);

        for (int i : cases) {
            solve(i);
        }
    }

    public static void solve(int n) {
        long printValue = (dp[n][1] + dp[n][2] + dp[n][3]) % MOD;
        System.out.println(printValue);
    }

    public static void buildDP(int n) {
        dp = new long[n + 1][4]; 
        
        // dp 초기값 설정
        dp[1][1] = 1;
        dp[2][1] = 0; // 2까지 도달했을 때 마지막으로 밟은 게 1일 경우
        dp[2][2] = 1; // 2까지 도달했을 때 마지막으로 밟은 게 2인 경우
        dp[2][3] = 0;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;
        
        // 점화식
        for (int i = 4; i <= n; i++) {
            // 1로 끝나는
            dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
            // 2로 끝나는
            dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
            // 3으로 끝나는
            dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
        }
    }
}

[문제 풀이 설명]

일단 DP (다이나믹 프로그래밍) 문제는 점화식을 찾는 것이 중요하다. 그리고 dp배열을 1차원으로 구현할지 또는 2차원으로 구현할지 잘 생각해 봐야한다.

(다들 9095번 (1, 2, 3 더하기)을 풀었을 거라 예상하고 설명을 하겠다.)
위 문제의 핵심은 "단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다."이다.

예를 들어서 n이 4인 경우,

1: 1
2: 2
3: 1+2, 2+1, 3
4: 1+3, 3+1
...

이렇게 나열해 볼 수 있다. 문제의 규칙 때문에 4일 때 (2+2)는 같은 수(2)가 연속해서 사용되므로 경우의 수에서 제거해야 한다.

따라서! 이 문제는 dp를 2차원 배열로 구성하고, 2번째 인자에는 마지막으로 밟고 온 수를 저장하면 된다. 예를 들어서 dp[2][1]은, 2까지 도달했을 때 마지막으로 1을 거쳐왔다는 뜻이다.

따라서 초기값 설정은 1부터 3까지 각각 무엇을 밟아서 도달했는지를 저장해주고,

dp[1][1] = 1;
dp[2][1] = 0; // 2까지 도달했을 때 가장 마지막으로 1을 지나옴.
dp[2][2] = 1; // 2까지 도달했을 때 가장 마지막으로 2를 지나옴.
dp[2][3] = 0;
dp[3][1] = 1;
dp[3][2] = 1;
dp[3][3] = 1;

점화식은 끝나는 값에 맞춰서 그 값이 아닌 값으로 거쳐와야 하므로 해당 경우의 수들의 합을 구하고, 문제에 나와있듯이 방법의 수를 MOD(1,000,000,009)로 나눈 나머지를 저장하면 된다.

for (int i = 4; i <= n; i++) {
	// 1로 끝나는
	dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;
    // 2로 끝나는
	dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;
	// 3으로 끝나는
	dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;
}

[어려웠던 점]

우선 dp를 1차원으로 해결하려 했었다. 아무래도 1차원은 거쳐온 경로를 저장할 수 있는 방법이 없으므로 어렵다.
그리고 문제를 대충(?) 봐서 MOD 값으로 나눈 나머지를 구해야 한다는 것을 몰라 계속 틀렸었다.

[느낀점]

문제를 꼼꼼히 읽자! 그리고 경우의 수를 직접 써가면서 규칙을 찾아가자.