[BOJ/DP] 백준 2225 - 합분해 (Java)

2225 - 합분해

https://www.acmicpc.net/problem/2225

문제

0 ~ N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수
덧셈의 순서가 바뀐 경우는 다른 경우 ex. 1 + 2 != 2 + 1
/ 한 개의 수를 여러 번 사용할 수 있음

입력: 정수 N (1 <= N <= 200), K (1 <= K <= 200)
출력: 답을 1,000,000,000으로 나눈 나머지

---

풀이

• `dp[i][j]`: 정수 j개를 더해서 합이 i가 되는 경우의 수

 

• `dp[0][i] = 1`: i로 0을 만드는 방법 1가지 
  • `dp[0][1] =  1`: 정수 1개로 0을 만드는 방법: 0 => 1가지

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

 

• `dp[i][j] = dp[i][j - 1] + dp[i - 1][j]`
  • `dp[i][j - 1]`: j - 1개 정수로 합이 i가 되는 경우의 수
    • 마지막에 0을 추가해서 j개로 만든 것
    • ex. [3, 2] -> 합 5 (j = 2) => [3, 2, 0] -> 합 5 (j = 3)
  • `dp[i - 1][j]`: j개 정수로 합이 i - 1가 되는 경우의 수
    • 이 수에 마지막 수 1을 추가하면 합이 i가 됨
    • ex. [2, 2] -> 합 4 (j = 2) => [2, 2, 1] -> 합 5 (j = 3)

---

예시

N = 5, K = 3

-> 3개의 정수로 합이 5가 되는 경우

• dp[1][1]: 합 1 / 개수 1 
  • dp[1][0] + dp[0][1] = 0 + 1 = 1
  • [1]
• dp[1][2]: 합 1 / 개수 2
  • dp[1][1] + dp[0][2] = 1 + 1 = 2
  • [1,0], [0,1]
• dp[1][3]: 합 1 / 개수 3
  • dp[1][2] + dp[0][3] = 2 + 1 = 3
  • [1,0,0], [0,1,0], [0,0,1]
• dp[2][1] 
  • dp[2][0] + dp[1][1] = 0 + 1 = 1
  • [2]
• dp[2][2]
  • dp[2][1] + dp[1][2] = 1 + 2 = 3
  • [2,0], [1,1], [0,2]
• dp[2][3]
  • dp[2][2] + dp[1][3] = 3 + 3 = 6
  • [2,0,0], [1,1,0], [1,0,1], [0,2,0], [0,1,1], [0,0,2]
• dp[3][1]
  • dp[3][0] + dp[2][1] = 0 + 1 = 1 
  • [3]
• ....dp[5][3]
  • dp[5][2] + dp[4][3] = 6 + 15 = 21

---

코드

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

// 합분해
public class boj_2225 {
    static int MOD = 1_000_000_000;

    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];
        for (int i = 1; i <= K; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
            }
        }

        System.out.println(dp[N][K]);
    }
}