[백준] 2225번 합분해 C++ 코드

코드

#include <iostream>
#include <cstring>

using namespace std;
typedef long long ll;
const ll MOD = 1000000000;

ll n,k,dp[203][203];

ll go(int sum,int cnt) {
    if(sum > n) return 0;
    if(cnt == k) {
        return sum == n ? 1 : 0;  // 합이 일치하면 1, 아니면 0 반환
    }
    ll &ret = dp[sum][cnt];
    if(ret != -1) return ret; // 메모이제이션
    ret = 0;
    for(int i = 0; i < n + 1; i++) {
        ret += (go(sum + i, cnt + 1)%MOD);
    }
    return ret % MOD;
}

int main() {
    cin >> n >> k;
    memset(dp, -1, sizeof(dp));
    cout << (go(0,0)%MOD) << '\n';
    
    return 0;
}

풀이

합을 분해하는 경우의 수를 찾는 문제이다. 처음에 idx까지 저장했다가 시간초과나서 문제 인식을 했다. 인덱스는 현재 어디까지 와있는지 알기 위한 장치이지, 저장할 필요는 없었다. 상태를 알기위해서는 합과 경우의 수만 저장하면 된다. 따라서 dp 테이블을 dp[sum][cnt]로 구성했고, 0부터 n까지 더했을 때의 케이스를 찾아주었다.