Baekjoon 2225번 합분해

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n, k;
int cache[201][201];

int dp(int cnt, int sum){
    // 기저 사례
    if(cnt == k && sum == n)
        return 1;
    // 메모이제이션
    int& ret = cache[cnt][sum];
    if(ret != 0)
        return ret;
    // 재귀 호출
    for(int i = 0; i <= n; i++)
        if(cnt < k && sum+i <= n){
            ret += dp(cnt+1, sum+i);
            ret %= 1000000000;
        }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    memset(cache, 0, sizeof(cache));
    cout << dp(0, 0);
    return 0;
}

재귀 호출 부의 if 문 누적합 조건을 잘못 입력하는 실수가 있었다.

반환값이 아닌 결과값을 10억으로 매 단계마다 나눠 주어야 했던점이 기억에 남는 문제.

다른 풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, k;
int D[201][201];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 1; i <= k; i++)
        D[i][0] = 1;
    for(int j = 0; j <= n; j++)
        D[0][j] = 0;
    for(int i = 1; i <= k; i++)
        for(int j = 1; j <= n; j++){
            D[i][j] = D[i-1][j] + D[i][j-1];
            D[i][j] %= 1000000000;
        }
    cout << D[k][n];
    return 0;
}

반복 dp 로 다시 풀어보았다.