[백준 2225 : JAVA] 합분해 / DP

문제

---

 

 

 

풀이

---

DP의 핵심 중 하나는 초깃값 설정이다. 

 

해당 문제는 0~N까지의 수열에서 K개의 정수를 선택해 N을 만드는 경우의 수니까 K=1일 경우부터 가정하여 생각해보자.

1개의 수를 선택해 N을 만드는 경우의 수는 무조건 1개이다. (N이라는 수 하나를 선택해야 N을 만들 수 있다.)

 

K=2일 경우를 생각해보자. (N=6 이라 가정)

N=6 이라고 가정하면, [0, 1, 2, 3, 4, 5, 6] 이라는 수열에서 2개의 정수를 선택해 6을 만들기 위한 방법은 아래와 같은 규칙을 가진다.

[0, 1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6]

 

문제에서 (0, 6)을 선택하는 경우와 (6, 0)을 선택하는 경우는 다르다고 했으니, 2개를 선택해 N을 만드는 경우의 수는 N+1개이다. 

다음으로 K=3일 경우를 생각해보자.

위의 규칙을 이용하면 되는데, 예를 들어 2개를 선택해 6을 만드는 경우 중 하나가 (2, 4)를 선택하는 것이다.

 

그렇다면, 2를 선택했을 때 6을 만들기 위한 수는 4라는 수 하나다. 그럼 2개의 수를 선택해 2라는 수를 만들면, 6을 만들기 위한 나머지 수 하나는 고정되어 있으니, 답을 구할 수 있지 않을까?

// DP[K][N] : K개의 수를 선택해 N이라는 수를 만들 수 있는 경우의 수.
DP[3][6] = DP[2][2];

 

그런데 위와 같은 규칙은 2라는 수뿐만 아니라, 0~N 수 모두에게 적용할 수 있다. 따라서, 다음과 같아진다.

// 2개의 수를 선택해 0을 만들면, 6을 만들기 위해 선택할 수 있는 수는 하나다.
DP[3][6] = DP[2][0] + DP[2][1] + DP[2][2] + ... + DP[2][6];

 

 

 

코드

---

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

public class Main {

    private static final int MOD = 1_000_000_000;
    private static int N, K;
    private static long[][] cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        cache = new long[K + 1][N + 1]; // [정수의 갯수][만들고자하는 수]

        // 1. i개 수를 선택해서 0을 만드는 경우는 무조건 0을 선택하는 한 가지 방법뿐.
        for (int i = 1; i <= K; i++) {
            cache[i][0] = 1;
        }

        // 2. 1개의 수를 선택해 i라는 수를 만들기 위해선 i라는 수를 선택하는 한 가지 방법뿐.
        for (int i = 0; i <= N; i++) {
            cache[1][i] = 1;
        }

        // 3. 2개의 수를 선택해 i라는 수를 만들기 위해선 0~i 까지의 경우의 수를 가진다.
        for (int i = 1; i <= N; i++) {
            cache[2][i] = i + 1;
        }

        // dp[K][N] = dp[K-1][0] + ... + dp[K-1][N]
        for (int i = 3; i <= K; i++) { // 선택할 수 있는 수의 갯수
            for (int j = 1; j <= N; j++) { // 만들고자하는 수
                for (int k = 0; k <= j; k++) {
                    cache[i][j] += (cache[i - 1][k]) % MOD;
                }
            }
        }

        System.out.println(cache[K][N] % MOD);
    }
}