2225번 : 합분해(점화식의 중요성)

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

2225번: 합분해

 

 

규칙을 찾아보려고 했을 때 쉽지 않았다. DP에서 가장 중요한 것은 점화식이 아닐까...

 

 

우선 점화식이 찾는 습관부터 들이도록 하자.

 

 

 

---

 

 

하향식 접근으로 간단하게 문제를 풀어보았다.

 

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int N, K;
long long dp[201][201];
long long solve(int N, int K) {
    if (K == 1)
        return 1;
 
    if (dp[N][K] != -1)
        return dp[N][K];
 
    dp[N][K] = 0;
    for (int i = 0; i <= N; i++)
        dp[N][K] = ((dp[N][K]) + (solve(N - i, K - 1) % 1000000000)) % 1000000000;
 
    return dp[N][K];
}
int main(void) {
    cin >> N >> K;
    memset(dp, -1, sizeof(dp));
    cout << solve(N, K) << endl;
    return 0;
}