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

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

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static final int DIVISOR = 1000000009;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        long[][] dp = new long[100001][4];
        dp[1][1] = 1; // 1
        dp[2][2] = 1; // 2
        dp[3][1] = 1; // 2+1
        dp[3][2] = 1; // 1+2
        dp[3][3] = 1; // 3

        for(int i=4; i<100001; i++){
            dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % DIVISOR; // 2로 끝난 수식에서 1더하는 경우의 수 + 3으로 끝난 수식에서 1더하는 경우의 수
            dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % DIVISOR; // 1으로 끝난 수식에서 2더하는 경우의 수 + 3으로 끝난 수식에서 2더하는 경우의 수
            dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % DIVISOR;  // 1로 끝난 수식에서 3더하는 경우의 수 + 2로 끝난 수에서 3더하는 경우의 수
        }

        int T = Integer.parseInt(br.readLine());

        while(T-->0){
            int n = Integer.parseInt(br.readLine());
            sb.append((dp[n][1] + dp[n][2] + dp[n][3]) % DIVISOR).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

1,2,3 더하기 문제와 비슷한데, 이 문제에서 달라진 점은 어떤 수를 1, 2, 3의 합으로 나타냈을 때 바로 이전에 사용한 숫자를 그 다음에 사용하지 못한다는 것이다. 
그러므로 바로 이전 숫자에서 더하는데 1을 사용했는지, 2를 사용했는지, 3을 사용했는지 체크해서 경우를 나눠줘야 한다. 

 

이 점이 어려워 구글링해 아이디어를 참고했다.

dp를 우선 이차원 배열로 만들어 n을 표현할 수 있는 연산 중 마지막이 1로 끝나는지, 2로 끝나는지, 3으로 끝나는지에 따라

dp[n][1], dp[n][2], dp[n][3] 으로 표현한다.

 

1로 끝나는 연산 = 2로 끝나는 수식에서 1을 더하는 경우의 수  + 3으로 끝나는 수식에서 1을 더하는 경우의 수 

2로 끝나는 연산 = 1로 끝나는 수식에서 2를 더하는 경우의 수 + 2로 끝나는 수식에서 2를 더하는 경우의 수

3으로 끝나는 연산 = 1로 끝나는 수식에서 3을 더하는 경우의 수 + 2로 끝나는 수식에서 3을 더하는 경우의 수

 

이를 점화식으로 이렇게 표현할 수 있다.

 

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]

 

이렇게 1, 2, 3으로 끝나는 연산을 각각 모두 더하면 총 구하고자 하는 경우의 수가된다. 

 

 

다음은 n = 7일 때의 연산 과정을 표로 나타낸 것이다.

 

 

	1	2	3	합
1	1	0	0	1
2	0	1	0	1
3	1	1	1	3
4	2	0	1	3
5	1	2	1	4
6	3	3	2	8
7	5	2	2	9