BOJ 2225 합분해

문제

 

 

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 복사

20 2

예제 출력 1 복사

21

---

해설

 

이 문제의 경우, 초반에 0 또한 수를 만드는 경우에 속하는 지 모르고, 삽질을 조금 했었다. 하지만 점화식으로 식을 이미 세워놨기 때문에 쉽게 문제를 찾아내 수정할 수 있었다.

 

먼저 이 문제의 점화식을 정리하면 다음과 같다.

D[n][k] = k개의 수로 n을 만드는 경우의 수
D[n][k] = D[n][k - 1] + D[n - 1][k - 1] + ... D[1][k - 1] + D[0][k - 1]

 

왜 이렇게 되는 지를 살펴보자.

 

예시에 나온 20 2를 적용해보자. 위 그림에서 i는 수이며, 네모 박스는 k - 1개로 만들 수 있는 경우로, 약간의 상상력 혹은 예시를 이용해 채워넣으면 이해가 좀 더 쉬울 것이다.
처음엔 i를 0으로 설정해보자.

그렇게 되면 네모 박스엔 20을 1개의 수를 이용해 만들 수 있는 경우가 채워질 것이다.

D[20][1] + 0의 형태가 될텐데, 이는 20을 2개로 만드는 방법 중 일부가 된다.
이제 i를 1로 설정해보자.

그렇게 되면 네모 박스엔 합이 1개의 숫자로 합이 19가 되는 경우가 채워져야 한다.

즉, D[19][1] + 1 또한  2개의 수로 20을 만드는 방법 중 일부에 속하게 된다.

이런식으로 i를 1씩 늘려가면 D[18][1] + 2 ... D[0][1] + 20은 모두 20을 두 수의 합으로 만드는 방법이 되는 걸 이해할 수 있다. 

 

그렇다면 다시 점화식을 살펴보자.

D[n][k] = D[n][k - 1] + D[n - 1][k - 1] + ... D[1][k - 1] + D[0][k - 1]

왜 i가 사라졌냐고 묻는다면, 아직 점화식을 제대로 이해하지 못하는 것이다. D는 방법의 수를 의미하기 때문에 위 그림에서 i는 설명을 위해 추가한 요소이지, 방법의 수에 직접 더하면 안 된다.

 

이를 기반으로 코드를 짜 보자.

 

import java.io.*;

public class Main {
    public static long[][] D;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        // D[n][k] = D[n][k - 1] + D[n - 1][k - 1] + ... D[1][k - 1] + D[0][k - 1]
        // n >= k 인 보장이 없다
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        D = new long[n + 1][k + 1];
        for(int i = 0; i <= k; i++){
            D[0][i] = 1;
        }
        makeD(n, k);
        System.out.println(D[n][k]);

    }
    public static void makeD(int n, int k){
        // 기저 사례 : k가 1이 아니면 배열을 아직 덜 채웠으므로 into
        if(k > 1){
            makeD(n, k - 1);
            long sum = D[0][k - 1];
            for(int i = 1; i <= n; i++){
                sum += D[i][k - 1];
                D[i][k] = sum % 1000000000;
            }
        } else {
            for(int i = 1; i <= n; i++){
                D[i][1] = 1;
            }
        }
    }
}

 

느낀 점

• 점화식을 이용해 깔끔하게 풀어냈다. 

 

아직 DP에서 점화식을 어떻게 다뤄야하는 지 모른다면?? 아래 글을 참고하자!!

 

2020/04/17 - [알고리즘 문제풀이/Java] - DP - 점화식의 중요성(BOJ 11052, 16194)