[백준] 15990번 1, 2, 3 더하기 5

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

 

같은 숫자가 2개 연속으로 나오면 안됨

숫자 n을 만들 수 있는 식 중 1로 끝나는 식은 dp[n][1]에, 2로 끝나는 식은 dp[n][2]에, 3으로 끝나는 식은 dp[n][3]에 담는다.

 

1.  7을 만들 수 있는 수식 중에서

1로 끝나는 수식(마지막에 1을 더해주는 경우) 은 

6을 만드는 수식에서 2로 끝나는 것에 1을 더하는 것,

6을 만드는 수식에서 3으로 끝나는 것에 1을 더하는 것

따라서 dp[7][1] = dp[6][2] + dp[6][3] 이다.

점화식 : dp[n][1] = dp[n-1][2] + dp[n-1][3]

 

2. 7을 만들 수 있는 수식 중에서

2로 끝나는 수식(마지막에 2를 더해주는 경우) 은

5를 만드는 수식에서 1로 끝나는 것에 2를 더하는 것,

5를 만드는 수식에서 3으로 끝나는 것에 2를 더하는 것

따라서 dp[7][2] = dp[5][1] + dp[5][3] 이다.

점화식 : dp[n][2] = dp[n-2][1] + dp[n-2][3]

 

3. 7을 만들 수 있는 수식 중에서

3으로 끝나는 수식(마지막에 3을 더해주는 경우) 은

4를 만드는 수식에서 1로 끝나는 것에 3을 더하는 것,

4을 만드는 수식에서 2로 끝나는 것에 3을 더하는 것

따라서 dp[7][3] = dp[4][1] + dp[4][2]

점화식 : dp[n[[3] = dp[n-3][1] + dp[n-3][2]

 

 

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        long[][] dp = new long[100001][4];

        dp[1][1] = 1; // 1
        dp[1][2] = 0;
        dp[1][3] = 0;

        dp[2][1] = 0;
        dp[2][2] = 1; // 2
        dp[2][3] = 0;

        dp[3][1] = 1; // 2 + 1
        dp[3][2] = 1; // 1 + 2 
        dp[3][3] = 1; // 3

        for(int i = 4; i <= 100000; i++) {
            // i-1을 만들 수 있는 숫자 중 맨 끝이 2 or 3인것
            dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1000000009;
            // i-2를 만들 수 있는 숫자 중 맨 끝이 1 or 3인것
            dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1000000009;
            // i-3을 만들 수 있는 숫자 중 맨 끝이 1 or 2인것
            dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1000000009;
        }

        for(int j = 0; j < t; j++) {
            int n = Integer.parseInt(br.readLine());
            long ans = (dp[n][1] + dp[n][2] + dp[n][3]) % 1000000009;
            sb.append(ans).append("\n");
        }

        System.out.println(sb);
    }
}