2225 합분해

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	30216	13236	9582	42.189%

문제

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

코드

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

public class P_2225 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[][] dp = new int[info[1] + 1][info[0] + 1];

        dp[0][0] = 1;
        for (int i = 1; i <= info[1]; i++) {
            for (int j = 0; j <= info[0]; j++) {
                for (int k = 0; k<= j; k++) {
                    dp[i][j] += dp[i - 1][j - k];
                    dp[i][j] %= 1000000000;
                }
            }
        }
        bw.write(Integer.toString(dp[info[1]][info[0]]));
        bw.flush();
    }
}

코드 내용

dp[i][j] = i개의 수를 이용해서 j를 만드는 경우의 수
n을 k개의 정수를 이용해서 구하는 방법은 k - 1개의 수를 이용해서 0 ~ n을 만드는 경우를 더한 것과 같다.
k - 1개의 수를 이용해서 0을 만들었을 경우에 k번째에 n을 더하면 조건을 충족하게 되고, k - 1개의 수를 이용해서 n을 만들었을 경우에 k번째에 0을 더하면 조건을 충족할 수 있기 때문이다.

그런데 dp[1][1]을 생각하면 dp[0][0] + dp[0][1]로 이루어지게 되는데 1을 dp의 시작 기준점으로 두었기 때문에 결과값이 0이 나오므로 dp[0][0]을 1로 초기화를 시켜두었다.