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

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

 

---

사고방식

1,2,3더하기 문제 시리즈의 다섯번째 문제이다. 

이번에는 n을 1,2,3의 덧셈으로 표현하는 과정에서 같은 수가 반복으로 나오면 안된다.

즉, n=4일 때, 1+2+1은 가능하지만 1+1+2는 1이 연속이어서 불가능하다. 

 

이를 해결해주기 위해 dp[i][f] 배열을 2차원배열로 짰다. 

단순히 이전 dp[i] 값들만 있으면 될 때는, dp[i]를 1차원으로만 짜면 됐지만 이번 문제는 이전 dp[i]값만 있으면 다음 dp[i+1] 값 등을 구할 때, 1,2,3을 각각 더해도 되는지, 즉, 이전 dp[i] 방법들이 1,2,3으로 끝나는 방법이 몇 개인지 알 수가 없기 때문에 이를 위해 dp[i][j] 2차원 배열로 짰다. 말이 어려우니 예시를 들어보겠다.

 

dp[4] 의 방법은 '1+2+1', '1+3', '3+1' 총 세가지이다. 

1,2,3더하기 첫 번째 문제와 같이 dp[5]를 구할 때는, dp[4]의 방법들에 1을 붙이면 된다. 즉, 

dp[5] 는 '1+2+1' +1, '1+3'+1, '3+1'+1 이런 식으로 dp[4]의 방법에 1을 더해주는게 가능한 경우의 수를 구하면 된다.

하지만 dp[4] 의 방법 3가지 중 1+2+1, 3+1 이 두가지는 1로 끝나므로 뒤에 1을 붙여줄 수가 없다. 따라서 dp[4]에 1을 붙여줘서 dp[5]의 방법을 만들어줄 수 있는 것은 1+3+1 한가지 뿐이다. 

이는 dp[i]를 1차원으로 짜면 안되고 dp[i][j] 2차원으로 짜야하는 이유이다.

i는 이전 문제와 같이 n의 값을 받는 것이고

j는 이 방법의 마지막 수가 몇인지를 나타낸다. 즉, 

 

dp[4]의 방법 '1+2+1', '1+3', '3+1' 으로 짜는게 아니라 

 

dp[4][1]의 방법 : '1+2+1', '3+1' (dp[4]의 방법 중에서 마지막 수가 1인 것들)

dp[4][2]의 방법 :                       (dp[4]의 방법 중에서 마지막 수가 2인 것들은 없으므로 0이다.)

dp[4][3]의 방법 : '1+3'               (dp[4]의 방법 중에서 마지막 수가 3인 것들)

 

로 짜는 것이다. 

이제 dp[5][1] 을 구할 때는, dp[4][1]에 1을 더하는 방식은 더해주면 안된다. dp[4][1]이라는 말 자체가 dp[4]를 구하는 방법 중에 1로 끝난다는 말이기 때문에 여기에 1을 연속으로 더해줄 수 없다. 따라서

dp[5][1] = dp[4][2] + dp[4][3]  이다.

같은 이유로

dp[5][2] = dp[3][1] + dp[3][3], 

dp[5][3] = dp[2][1] + dp[2][2]

이다. 

 

이제 점화식을 구해야 한다. 여기까지 이해했으면 점화식은 쉽다. 

dp[n][1] = (dp[n][2] + dp[n][3]) % 1000000009

dp[n][2] = (dp[n][1] + dp[n][3]) % 1000000009

dp[n][3] = (dp[n][1] + dp[n][2]) % 1000000009

 

---

결론

dp[n][1] = (dp[n-1][2] + dp[n-1][3]) % 1000000009

dp[n][2] = (dp[n-2][1] + dp[n-2][3]) % 1000000009

dp[n][3] = (dp[n-3][1] + dp[n-3][2]) % 1000000009

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int arr[] = new int [n+1];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        long dp[][] = new long [100001][4];
        dp[1][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;
        
        for(int i=0; i<n; i++){
            for(int j=4; j<=arr[i]; j++){
                dp[j][1] = (dp[j-1][2] + dp[j-1][3]) % 1000000009;
                dp[j][2] = (dp[j-2][1] + dp[j-2][3]) % 1000000009;
                dp[j][3] = (dp[j-3][1] + dp[j-3][2]) % 1000000009;
            }
        }
        
        for(int i=0; i<n; i++){
            System.out.println((dp[arr[i]][1] + dp[arr[i]][2] + dp[arr[i]][3]) % 1000000009);
        }
    }
}