b2225. 합분해

 

 

 

✨ 자바로 푸는 합분해 문제 풀이

 

---

 

📌 문제 개요

 

정수 N과 정수 K가 주어졌을 때,

정수 N을 K개의 정수의 합으로 나타내는 경우의 수를 구하는 문제입니다.

 

단, 0도 정수에 포함되며, 순서가 다른 것은 다른 경우로 칩니다.

 

---

 

💡 예제 입력

20 2

 

💡 예제 출력

21

 

---

 

🛠 알고리즘 접근 방식

 

이 문제는 전형적인 DP(동적 계획법) 문제입니다.

 

dp[n][k] = 정수 n을 k개의 정수 합으로 표현하는 경우의 수

 

---

 

🔸 점화식 아이디어

 

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

 

• dp[n-1][k]: 마지막 수가 1 이상일 때, 전체 합에서 1을 빼고 다시 나누는 경우
• dp[n][k-1]: K-1개의 정수로 n을 만들고 마지막에 0을 더하는 경우

 

---

 

✅ 핵심 초기값

 

• dp[1][i] = i
• (1을 i번 사용하는 경우: 1+0+0+…+0)
• dp[i][1] = 1
• (i를 하나의 수로 표현하는 방법은 단 하나뿐)

 

---

 

🧾 코드 해설

dp = new int[N+1][M+1];

for (int i = 1; i <= M; i++) {
    dp[1][i] = i; // 1을 i개의 수로 표현하는 경우
}
for (int i = 1; i <= N; i++) {
    dp[i][1] = 1; // i를 1개의 수로 표현하는 경우
}

 

• 초기 조건 세팅

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

 

• 점화식 구현 (중복 방지 위해 mod 1,000,000,000)

 

---

 

✅ 핵심 포인트 정리

 

• 순서가 다르면 다른 경우로 취급되므로 중복 허용 DP
• dp[n][k] = dp[n-1][k] + dp[n][k-1] 로 구성
• 메모이제이션 또는 bottom-up으로 효율적 해결
• 출력 시 1,000,000,000으로 나눈 나머지를 출력

 

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

public class Main {

    static int N, M;
    static int[][] dp; // i까지의 정수 j개를 더해서 그합이 i 되는 경우의 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for(int i = 2; i <= M ; i++){
            for(int j = 2 ; j <= N ; j++){
                dp[j][i] = (dp[j-1][i] + dp[j][i-1])%1000000000;
            }
        }
        System.out.println(dp[N][M]);
    }
}