[Gold V] 합분해 - 2225

[문제 위치]

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

 

[문제 풀이]

점화식을 바탕으로 해서 다이나믹 프로그래밍을 하는 문제이다.

 

일단 문제를 작게 쪼개야 한다. 이 문제도 다른 DP 문제와 비슷하다.

 

N개의 숫자를 사용하여 K를 만들어야 한다.

이는 N-1개의 숫자를 사용하여 K-x(x는 임의의 정수)를 만들고 x를 더해주는 것과 같다.

 

따라서 N-1개의 숫자로 만들 수 있는 K-x의 경우의 수를 모두 더하면 이것이 N-1개의 숫자로 K개의 숫자를 만들 수 있는 경우의 수가 되는 것이다.

 

이를 점화식으로 표현하면 다음과 같다.

 

이를 바탕으로 가장 작은 수에서 점점 올라가며 다이나믹 프로그래밍 구조를 채워나간 다음 dp[N][K]를 호출하면 N개의 숫자로 K를 만드는 경우의 수를 알 수 있다.

 

아래는 이를 코드로 작성한 것이다.

 

#include <iostream>
#include <vector>

#define MOD 1000000000
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

// DP 테이블 초기화
int dp[201][201] = { 0 };

int main() {
    fastio;
    int n, k;
    cin >> n >> k;

    // 초기값 설정: dp[0][0] = 1
    dp[0][0] = 1;

    // DP 배열 채우기
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            for (int x = 0; x <= j; x++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD;
            }
        }
    }

    // 결과 출력
    cout << dp[k][n] << endl;

    return 0;
}