[백준] 2225번 합분해

문제

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

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

입력

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

출력

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

---

풀이

다이나믹 프로그래밍으로 풀이가 가능하며 점화식은 아래와 같이 도출 할 수 있다.

dp[n][k] : n개의 정수 k개를 합하여 그 합이 n이 되는 경우의 수

n\k	1	2	3	4	5	6	j
1	1	2	3	4	5	6	j
2	1	3	6	10
3	1	4	10
4	1	5
5	1	6
6	1	7
I	1						dp[i-1][j] + dp[i][j-1]

소스 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int result = solution(n, k);
        System.out.println(result);
    }
    public static int solution(int n, int k) {
        int[][] dp = new int[n+1][k+1];

        for (int i = 1; i <= n; i++) {
            dp[i][1] = 1;
        }
        for (int j = 1; j <= k; j++) {
            dp[1][j] = j;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1_000_000_000;
            }
        }

        return dp[n][k];
    }
}

문제 출처 : www.acmicpc.net/problem/2225

2225번: 합분해