백준 15990 자바 - 1, 2, 3 더하기 5

문제

---

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

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

 

 

 

문제해결

---

- 같은 숫자가 2개 연속으로 나오면 안되기 때문에 dp 배열을 2차원 배열로 만든다

 

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

- dp[n][1]에는 i-1을 만들수 있는 식 중 2로 끝나는식, 3으로 끝나는 식 개수를 넣는다

- dp[n][2]에는 i-2를 만들수 있는 식 중 1로 끝나는식, 3으로 끝나는 식 개수를 넣는다

- dp[n][3]에는 i-3을 만들수 있는 식 중 1로 끝나는식, 2로 끝나는 식 개수를 넣는다

 

- 점화식

dp[n][1] = dp[n-1][2] + dp[n-1][3];

dp[n][2] = dp[n-2][1] + dp[n-2][3];

dp[n][3] = dp[n-3][1] + dp[n-3][2];

 

- n = 4 일때

dp[4][1] = 3을 만들수 있는 식 중, 2로 끝나는식(dp[3][2]) + 3으로 끝나는 식(dp[3][3])

dp[4][2] = 2를 만들수 있는 식 중, 1로 끝나는식(dp[2][1]) + 3으로 끝나는 식(dp[2][3])

dp[4][3] = 1을 만들수 있는 식 중, 1로 끝나는식(dp[1][1]) + 2로 끝나는 식(dp[1][2])

그리고 dp[4][1] + dp[4][2] + dp[4][3] 을 하면 같은 수를 2번씩 쓰지 않고 만들수 있는 개수를 구할 수 있다

import java.util.Scanner;

public class B15990_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //i를 만들 수 있는 것 중 1로 끝나는것, 2로 끝나는것, 3으로 끝나는걸 각각 2차원 배열에 담는다
        int[][] dp = new int[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;
        }
        int t = sc.nextInt();
        //n을 만들기 위한 총 숫자 개수 = 1로 끝나는것 + 2로 끝나는것 + 3으로 끝나는것
        for (int i = 0; i < t; i++) {
            int n= sc.nextInt();
            int sum = 0;
            sum +=dp[n][1];
            sum%=1000000009;
            sum+=dp[n][2];
            sum%=1000000009;
            sum+=dp[n][3];
            sum%=1000000009;
            System.out.println(sum);
        }
    }
}