(C++) - 백준(BOJ) 2225번 : 합분해

www.acmicpc.net/problem/2225

2225번: 합분해

dp로 푼 문제였습니다.

 

풀이방법

 * 200까지의 수를 200개까지 뽑을 수 있기 때문에 순열로 접근하시면 시간초과를 맛볼 수 있습니다.

 

 1. k개로 n을 만드는 경우의 수를 저장할 d배열을 선언해줍니다.

 

 2. k-1개로 n-x수를 만드는 경우의 수들을 모두 더한다면 마지막으로 x를 사용했을 때 n을 만들 수 있습니다. 따라서 점화식을 세우면 다음과 같습니다.

d[i][j] = sum(d[i-1][0 ~ j ~ n])

 

 

Code

#include <bits/stdc++.h>
#define MOD 1'000'000'000
#define ll long long
using namespace std;
ll n,k;
ll d[201][201];
ll dp(ll k, ll n){
    if(k == 1) return 1;
    ll &ret = d[k][n];
    if(ret != -1) return ret;
    ret = 0;
    for(ll t = 0; t <= n; t++) ret += dp(k-1,t) % MOD;
    return ret % MOD;
}
int main(){
    cin >> n >> k;
    memset(d,-1,sizeof(d));
    cout << dp(k,n) << '\n'; 
}