BOJ 2225 합분해

https://www.acmicpc.net/problem/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

예제 입력 2

6 4

예제 출력 2

84

---

코드

K∖N	0	1	2	3	4	5
1	1개	1개	1개	1개	1개	1개
2	1개	2개	3개	4개	5개	6개
3	1개	3개	6개	10개	15개	21개
4	1개	4개	10개	20개	35개	56개
…

규칙을 찾으려고 조금 오래 생각했었다.

위 표에서 볼 수 있는 것처럼 K와 N에 따른 경우의 수를 cases[K][N]이라고 표현해보면 아래와 같은 규칙이 있다는 것을 알 수 있다.

cases[K][N] = cases[K][N - 1] + cases[K - 1][N]

예를 들면, cases[4][5] = 35개(cases[4][4]) + 21개(cases[3][5]) = 56개라는 것을 알 수 있다.

실제 구현에서는 K가 0인 경우는 고려할 필요가 없어서 첫 번째 인덱스부터 1에 해당하는 값으로 초기화했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int answer = countCases(N, K);

        System.out.println(answer);
    }

    static int countCases(int N, int K) {
        int[][] cases = new int[K][N + 1];
        Arrays.fill(cases[0], 1);
        for (int i = 1; i < K; i++) {
            cases[i][0] = 1;
            for (int j = 1; j <= N; j++) {
                cases[i][j] = (cases[i][j - 1] + cases[i - 1][j]) % 1_000_000_000;
            }
        }

        return cases[K - 1][N];
    }
}