[백준 2225] 합분해 / 자바 / dp **

문제         

레벨: G5
알고리즘: dp(업데이트 기준 2개 + 이차원 배열)
풀이시간: 1시간
힌트 참조 유무: 유

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

1 번째 시도   

[의문점]

1. 바로 숫자 N까지 가졌을 때를 구하면 되지 않나? ....N-2,N-1,N 차례차례 누적합으로 구해야 하나?
arr[N-1]가 arr[N] 만드는데 영향을 미치나?

2. 바로 K일 때를 구하면 되지 않나? ....K-2, K-1,K 차례차례 누적합으로 구해야 하나?

예를 들어 생각해보자
N = 3  K =3 

K가 0인 상황을 먼저 구해보자면
arr[0] = 0
arr[1] = 0
arr[2] = 0
arr[3] = 0

K가 1인 상황을 먼저 구해보자면
arr[0] = 1 {0} 
arr[1] = 1 {1}
arr[2] = 1 {2}
arr[3] = 1 {3}

K가 2인 상황을 구해보자
arr[0] = 1 {0,0} 
arr[1] = 2 {0,1} {1,0}
arr[2] = 3 {0,2} {2,0} {1,1}
arr[3] = 4 {1,2} {2,1} {3,0} {0,3}

K가 3인 상황을 구해보자
arr[0] = 1 {0,0,0}
arr[1] = 3 {1,0,0} {0,1,0} {0,0,1}
arr[2] = 6 {1,1,0} {0,1,1} {1,0,1} {0,2,0} {0,0,2} {2,0,0}
arr[3] = 10 {1,1,1} {2,1,0} {2,0,1} {1,2,0} {0,2,1} {1,0,2} {0,1,2} {3,0,0} {0,3,0} {0,0,3}

 

1번째 질문(arr[N-1]가 arr[N] 만드는데 영향을 미치나?)에 대한 대답은 YES다 
arr[N-1]의 답이 arr[N] 포함되어 있기 때문이다.

2번째 질문(바로 K일 때를 구하면 되지 않나? ....K-2, K-1,K 차례차례 누적합으로 구해야 하나?)에 대한 대답은 YES다 

그렇다면 업데이트 기준은 2개 + 이차원 배열을 활용한 dp 문제라는 결론에 도달했다.


K가 3일때  arr[3]은 (K가2인 arr[3]) + (K가 3인 arr[2])이다. 이로써 우리는 점화식을 구할 수 있다.

 

개인적인 Tip)

dp 문제를 풀 때 점화식을 이해하려고 하지 않는다. 오로지 값비교를 통해서 이 값이 이전에 dp[]에서 어떤 값들을 더해서 만들어줄 수 있는지 생각한다. 물론 이해하는 게 정석이고 그렇게 해야만 한다. 그러나 나는 이해력이 더디다 생각하여 지금은 임시방편으로 이렇게 점화식을 구한다.

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

public class Main {

    static int MOD = 1000000000;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        int dp[][] = new int[K+1][N+1];

        // Initialization
        for (int i = 0; i <= K; i++) {
            dp[i][0] = 1; // 1 way to distribute 0 items into i bins
        }

        for (int j = 0; j <= N; j++) {
            dp[0][j] = 1; // 1 way to distribute j items into 0 bins
        }

        // Fill the DP table
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
        }

        System.out.println(dp[K][N]);
    }
}