[백준] #2225 합분해 - JAVA

❔ 문제

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 42

예제 출력2

84

🔍 문제 풀이

이 문제는 최종 합 N 을 만들기 위해 분해 후 조합하는 문제로 DP로 해결해야한다.

<점화식 유도>

dp[k][n] = 정수 n을 k개의 수로 만드는 경우의수

- 베이스 케이스

dp[1][n] = 1 :1개의 수로 n을 만드는 방법은 단 한가지 뿐이다. (20 -> 20)
dp[k][0] = 1 : 0을 만드는 방법은 모두 0을 고르는 한 가지 뿐이다.

- 점화식 구성

아래 표는 k와 n의 값에 따른 경우의 수이다.

k/n	0	1	2	3
1	0	1	2	3
2	(0,0)	(0,1) (1,0)	(0,2) (1,1) (2,0)	(0,3) (1,2) (2,1) (3,0)
3	(0,0,0)	(0,0,1) (0,1,0) (1,0,0)	(0,0,2) (0,1,1) (0,2,0) (1,0,1) (1,1,0) (2,0,0)	(0,0,3) (0,1,2) (0,2,1) (0,3,0) (1,0,2) (1,1,1) (1,2,0) (2,0,1) (2,1,0) (3,0,0)

예를들어, n=2, k=3로 3개의 숫자로 2를 만든다고 한다.

1. dp[k-1][n]: 숫자 하나를 0으로 고정
   숫자 3개로 2를 만드는데, 숫자 하나를 0으로 확정한다.

• k = 2, 2개의 숫자로 2를 만들면 나머지 하나는 자동으로 0이다.
  즉, k-1개의 숫자로 n을 만든 경우와 동일하다
• k=2 -> (0,2) (1,1) (2,0) 에 각각 0을 추가한다면 아래와 같다.
  (0,2,0) (1,1,0) (2,0,0)

2. dp[k][n-1] : N을 N-1로 줄인 후 1을 더한다.
   숫자 개수는 3개로 유지하고, 2를 1로 줄인다.

• n=1, k=3 -> (0,0,1) (0,1,0) (1,0,0) 에 1을 더하면 아래와 같다.
  (0,0,2) (0,1,1) (1,0,1)

따라서 1번과 2를 조합하면,
(0,2,0) (1,1,0) (2,0,0) (0,0,2) (0,1,1) (1,0,1) 로
n=2, k=3일 때의 경우와 같게 나온다.

즉, 점화식을 아래와 같이 유도할 수 있다

dp[k][n]=dp[k−1][n]+dp[k][n−1]

☑️ 최종 코드

import java.io.*;
public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String [] input  = br.readLine().split(" ");
    int n = Integer.parseInt(input[0]);
    int k = Integer.parseInt(input[1]);

    long[][] dp = new long[k+1][n+1];

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


    for(int i = 1; i <= k; i++){
      for(int j = 0; j <=n;j++){
        if(j==0) {dp[i][j] = 1;}
        else{dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1_000_000_000;}
      }
    }
    System.out.println(dp[k][n]);

  }
}