백준 2225 합분해 (dp)

문제

2225번: 합분해 (acmicpc.net)

2225번: 합분해

 

풀이과정

0~N까지 숫자 중 K개를 더했을 때 N이 되는 경우의 수를 구하는 문제입니다.

또한 1+2 = 3 또는 2+1 = 3 두가지 경우 모두 가능 하다고 적혀있습니다.

 

완전탐색을 사용하기엔 시간적으로 불가능해 보이기 때문에 cache에 저장하는 dp를 사용했습니다.

점화식을 세우기 위해 생각해본 것은, 예를 들어, 간단하게 k = 2 , n = 3 인 경우입니다.

cache[k][n] = k개를 더했을 때 합이 n이 되는 경우의 수 저장

이렇게 정의를 해 봤을 때,

1. cache[1][3] 은 숫자 1개를 더했을 때 합이 3이되는 경우의 수를 저장하는 게 됩니다.

당연히 숫자 3 하나를 더했을 것이고, 만약 k = 2 라면 "0"을 더 더해주면 됩니다.

그런데 마지막에 0을 더해주는 것은 생각할 필요가 없습니다. 무조건 어떤 숫자 하나를 추가로 더해줘야만 하기 때문에

경우의 수를 구하는 데에는 영향을 미치지 않기 때문입니다.

 

나머지 경우 모두 작성해보겠습니다.

2. cache[1][2] 는 당연히 숫자 2 하나를 더하는 것이며

k = 2일 경우 숫자 "1"을 추가로 더해줘야 합니다.

 

3. cache[1][1] 은 당연히 숫자 1 하나를 더하는 것이며

k = 2일 경우 숫자 "2"를 추가로 더해줘야 합니다.

 

4. cache[1][0] 은 당연히 숫자 3 하나를 더하는 것이며

k = 2일 경우 숫자 "0"을 추가로 더해줘야 합니다.

 

따라서 점화식은

cache[k][n] = cache[k-1][n] + cache[k-1][n-1] + cache[k-1][n-2] + .... + cache[k-1][0]

이렇게 될 것입니다.

 

또한 고려해야 할 점은

k = 1 또는 n = 0 일 경우 경우의 수는 항상 1가지 뿐이라는 것입니다.

 

이 모든것을 고려해서 코드를 작성하면 되겠습니다. 

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
#define MOD 1000000000;
using namespace std;
int N,K;
// k개를 더했을 때 합이 n이되는 경우의수 저장
int cache[201][201];


// cache[k][n] = cache[k-1][n] + cache[k-1][n-1] ..... + cache[k-1][0]
int solution(int n, int k) {
    int &ret = cache[k][n];
    if(ret != -1) return ret;
    // 총 합이 0인 경우는 1가지 뿐
    if(n == 0) return ret = 1;
    // 1개를 더했을 때 n인 경우는 1가지 뿐
    if(k == 1) return ret = 1;

    // 초기값 0
    ret = 0;

    for(int i=n; i>=0; i--) {
        ret += solution(i,k-1);
        ret %= MOD;
    }
    return ret;
}

int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&N, &K);
    printf("%d\n",solution(N,K));
}