[백준 2225] 합분해

0. 제목

• 백준 2225 합분해
• BOJ 2225 합분해
• C++ 2225 합분해

---

1. 문제

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

---

2. 풀이

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.
• dp를 이용하였고 dp[K][N]의 의미는 K개의 수로 N을 만드는 경우의 수이다.
• 예를 들어, dp[3][30]을 구한다고 해보자.
• 3개로 30을 만들어야 하는 경우이고, 마지막에 더하는 수가 0이라면 2개로 30을 만드는 경우가 나올테고, 마지막에 더하는 수가 1이라면 2개로 29를 만드는 경우가 나올테고, 마지막에 더하는 수가 2라면 2개로 28을 만드는 경우가 나올테다.
• 위와 같이 쭉 나열해보면 다음과 같은 점화식이 나온다.
• dp[i][j] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j-1] + dp[i-1][j]
• 코드로 그대로 구현하고 구현 도중 1000000000 으로 나눈 나머지를 구하는 것에 유의하면 된다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int N, K;
    int dp[201][201] = {0};//dp[K][N] => K개로 N만들기
    
    cin >> N >> K;
    
    for(int i = 0; i <= N; i++){
        dp[1][i] = 1;
        dp[2][i] = i + 1;
    }
    
    for(int i = 3; i <= K; i++){
        for(int j = 0; j <= N; j++){
            for(int k = 0; k <= j; k++){
                dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % 1000000000;
            }
        }
    }
    cout << dp[K][N] << '\n';
    
    return 0;
}