[백준 2225번] [동적 계획법] 합분해

Approach

문제 자체는 쉬운데.. 문제를 잘못 읽어서 엄청 고생했다.

 

정수 k개를 더해서 합이 N이 되는 경우의 수를 구하는 상황이다. 그런데, 정수 k - 1개를 고른 상황에 대한 정보를 알면 구하고자 하는 경우의 수를 알 수 있는 느낌을 충분히 받을 수 있다. 이 지점에서 관계식을 포현할 수 있음을 인식하고, DP를 통해 이 문제를 해결할 수 있다는 것을 파악했으면 충분하다.

 

관계식 자체는 되게 단순하다.

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

dp[i][j] = $\sum\limits_k dp[i - 1][j - k]$ for $0\ge k \ge j$

(단, i가 1일때의 dp[i][j] = 1이고 dp[i][0] = 1로 항상 고려해주면 된다.)

 

특이 케이스들에 대해서만 조심해주면 쉽게 풀 수 있는 문제이다. 굳이 Top-down으로 내려올 필요가 없고, 이전 계산 결과를 단순히 활용하는 양상이므로 반복물을 통한 Bottom-up으로도 쉽게 해결할 수 있다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int n, k;
long long dp[201][201];

int main(void){
    fastio;
    fill(&dp[0][0], &dp[200][201], 0);
    
    cin >> n >> k;
    dp[0][0] = 1;

    for(int i = 1; i <= k; i++){
        for(int j = 0; j <= n; j++){
            if (i == 1){
                dp[i][j] = 1;
                continue;
            }
            if (j == 0)
            {
                dp[i][j] = 1;
                continue;
            }
            long long result = 0;
            for(int p = 0; p <= j; p++){
                result += dp[i - 1][j - p];
            }
            dp[i][j] += result % 1000000000;
            
            
        }
    }

    cout << dp[k][n] << "\n";
    return 0;
}