백준 2225 "합분해" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는  경우의 수를 구하는 문제.
• 순서가 달라도 같은 경우로 인정 (1+2와 2+1은 같은 경우).
• 한 개의 수를 여러 번 쓸 수 있음( 1+1 )
• 결과를 1,000,000,000으로 나눈 나머지를 출력, 

---

🛠 풀이 및 알고리즘

1. dp[k][n] 정의
   • `dp[k][n]`: n을 k개의 정수로 만드는 방법의 수.
2. 초기값 설정
   • `dp[1][n] = 1` → 하나의 숫자로 n를 표현하는 방법은 1개 (n 자체).
   • `dp[k][0] = 1` → 0을 k개로 만드는 방법은 0 + 0 + ... + 0 하나뿐.
3. 점화식 (DP)
   • `dp[k][n] = dp[k-1][n] + dp[k][n-1]`
     • `dp[k-1][n]` :  k-1개의 숫자로 n를 만드는 방법 ( `dp[k-1][n]` 에 0을 증가해주면 `dp[k][n]` ).
     • `dp[k][n-1]` : k개의 숫자로 n-1을 만드는 방법 ( `dp[k][n-1]`에 1을 증가해주면 ` dp[k][n]` )

① dp[1][3] (1개의 숫자로 3을 만드는 경우의 수)

• (3) ➡ dp[1][3] = 1

② dp[2][2] (2개의 숫자로 2를 만드는 경우의 수)③ 점화식 적용

• (0,2), (1,1),(2,0) ➡ dp[2][2] = 3

③ 점화식 적용 

• dp[2][3] = dp[1][3] + dp[2][2] = 1 + 3 = 4
• ➡ (0,3), (1,2), (2,1), (3,0)

---

💡 코드

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

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

        // 초기값 설정
        Arrays.fill(dp[1], 1); // 1개의 숫자로 n을 만드는 방법은 1개
        for (int i = 1; i <= k; i++) {
            dp[i][0] = 1; // 0을 i개의 숫자로 만드는 방법은 1개
        }

        // dp 점화식
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
                dp[i][j] %= 1000000000; // 교환법칙 성립
            }
        }
        System.out.println(dp[k][n] );
    }
}

---

🏆 시간 복잡도 분석

• O(KN)
•  N ≤ 200, M ≤ 200→ 최악의 경우 40,000