[백준/JAVA] BOJ 2225 - 합분해

dp 너무 어려워요
못하겠어요.....

👀 문제

2225번: 합분해 ✨ 골드 5

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

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

예제 입력

20 2

예제 출력

21

🔑 키포인트

다이나믹 프로그래밍

✍️ 코드

📍 dp[n][k] = 숫자 n을 k개를 이용해 만들 수 있는 경우의 수

💡 dp[n][k] = dp[n][k - 1] + dp[n - 1][k]
1. dp[n][k - 1]에 0을 붙이면 된다.
2. dp[n - 1][k]의 경우들에 1을 더해 주면 된다.

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

public class BOJ2225_합분해 {
    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[][] dp = new int[n + 1][k + 1];
        Arrays.fill(dp[0], 1);

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

        System.out.println(dp[n][k]);
    }
}