백준[2225] 합분해

문제 설명

문제 링크

http://icpc.me/2225

2225번: 합분해

풀이

dp를 이용하여 풀이할 수 있다.

dp [남은 수][뺄 수 있는 횟수]로 정의할 수 있다.

코드

#include <cstdio>

using ll = long long;

ll dp[202][202], N, K;
const ll mod = 1e9;

ll dpf(ll n, ll k) {
    ll &ret = dp[k][n];
    if (ret) return ret;
    // 남은 수와 뺄 수 있는 횟수가 0일때 1리턴
    if (!n && !k) return 1;
    // 뺄 수 있는 횟수는 끝났는데 수가 남아있을 때 0리턴
    if (n && !k) return 0;
    for (ll i = 0; i <= n; i++) {
        if (n - i >= 0) ret += dpf(n - i, k - 1) % mod;
    }
    return ret % mod;
}

int main() {
    scanf("%lld %lld", &N, &K);
    printf("%lld", dpf(N, K));
}