[boj] 백준 2225 합분해 (c++) - dp

[문제]

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

2225번: 합분해

 

[풀이]

(N-L) + L = N 이라고 생각해 볼 수 있다. 이전까지의 숫자 합에 N이 되게 하는 임의의 값 L을 더한 것이 되며, 이때 숫자합은 임의의 값을 제외한 K-1개의 숫자이다.  

즉, dp[k][n]가 n을 k개의 숫자로 만들 수 있는 경우의 수라고 하면, 점화식은 다음과 같다.

dp[k][n] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][n-2] + dp[k-1][n-1] + dp[k-1][n]

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 987654321

using namespace std;

int n, k;
long long dp[201][201];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    //dp[k][n] -> k개의 수를 더해 합이 n이 되는 경우의 수
    for(int i=0; i<=n; i++){
        dp[1][i] = 1;
    }

    for(int i=1; i<=k; i++){
        for(int j=0; j<=n; j++){
            for(int l=0; l<=j; l++){
                dp[i][j] += dp[i-1][j-l];
                dp[i][j] %= 1000000000;
            }
        }
    }

    cout << dp[k][n];

}