[C/C++] 백준 #2225 합분해(동적 계획법)

#2225 합분해 문제는 경우의 수를 찾는 문제입니다.  경우의 수를 찾는 문제들의 특성은 동적 계획법하고 상당히 잘 맞습니다.

문제는 동적 계획법을 어떻게 구성할 것인가죠.  그리고 꽤 많은 경우 간단하게 한번에 계산할 수 있는 경우의 수를 찾을 수도 있습니다.  물론 그것이 계승(factorial) 형태로 나오면 큰 의미도 없습니다.

 

문제의 링크입니다.

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

2225번: 합분해

문제의 요구사항은 간단합니다.  0부터 N까지의 수중에 K개를 뽑아서 합이 N을 만드는 경우의 수입니다.  중복된 수도 허용하고, 더하는 순서가 다르면 서로 다른 경우로 봅니다.  예를 들어서 \( 1+2 \)와 \(2+1\)은 서로 다른 경우로 봅니다.

 

 

이를 위해서 \(d_{k, n}\)이란 것을 정의합니다.  0부터 n까지의 숫자중에 k개를 뽑아서 n을 만들 수 있는 경우의 수입니다.

일단 n이 0이라면 무조건 경우의 수는 1이라고 할 수 있습니다.  만약 k가 0이라면, 0을 만드는 경우만 1, 나머지는 0이라고 정의하면 됩니다.

 

\[ d_{k, 0} = 1, ~~~~~~ d_{0, n} = 0 ~~~~~ ( n \ne 0 ) \]

 

기본 초기값을 정의를 했으니, 이제 점화식을 만들면 됩니다.  점화식은 다음과 같이 생각했습니다.  \(k-1\)개를 선택해서 n을 만들었다면, 여기에 0을 더하면 됩니다.  예를 들어서 \( 3 + 2 = 5 \)라는 식이 있다면, 여기에 0을 더하면 \( 3 + 2 + 0 = 5 \)가 됩니다.

다음으로는 \(k\)개를 선택해서 n-1을 만들었다면, 맨 마지막 수에 1을 더하면 n을 만들 수 있습니다.  왜 하필이면 맨 마지막 수에 1을 더하는가?  그 이유는 \(k-1\)개를 선택한 것에 0을 더하는 것을 맨 마지막에 추가하는 것으로 했기 때문입니다.

 

그래서 얻어지는 점화식은 다음과 같습니다.

 

\[ d_{k, n} = d_{k-1, n} + d_{k, n-1} \]

 

그러면 이것을 이용해서 프로그램을 작성하면 다음과 같습니다.  숫자의 범위가 꽤 커지게 나오므로, 오버플로우에 주의하여야 합니다.

//------------------------------------------------
//    baekjoon #2225
//        - by Aubrey Choi
//        - created at 2019-09-28
//------------------------------------------------
#include <stdio.h>

int main()
{
    int n,k;
    static unsigned dp[201][201];
    scanf("%d%d",&n,&k);
    dp[0][0]=1;
    for(int i=1;i<=k;i++)
    {
        dp[i][0]=1;
        for(int j=1;j<=n;j++) dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000;
    }
    printf("%u\n", dp[k][n]);
}