[동적프로그래밍] 백준 2225번 합분해(C++)

 

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

 

해당 문제는 어떤 정수 n에 대해서 k개의 갯수로 더해지는 횟수를 묻는 문제이다.

 

예를들어 1을 5개의 수로 나누기 위한 방법은?

 

1 0 0 0 0 

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1 

이렇게 총 5가지가 나오게 된다는 것이다.

그렇다면 n=1일때 모든 k에 대해서는 k의 값이 나오게 된다는 것이다. (1개의 1과 k-1개의 0 의 순서)

 

먼저 k=1일때 모든 숫자에 대해서 그 방법은 1이 나오게 될 것이다 

(자기 자신의 숫자만 더해지니)

그리고 n=2,k=2의 경우 1,1 / 2,0 / 0,2 로 3가지 방법이 있을 것이다.

n=3 k=2일때는?

1,2 /2,1/ 3,0 /0,3,

4가지다.

 

그래서 대충 경우의 수를 다 적어보면...

 

 

n↓               k →	1	2	3	4
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20

어랏? 

n↓               k →	1	2	3	4
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20

 

특정 n 과 k에 대해서 n-1일때 k의 값을 모두 더해주게 되면 n / k의 값이 나오네?

그렇다면 점화식은

Snk = Σn-1Si ( i=0 to k)

그렇다면 이걸 식으로 써주게 되면

 

#include <iostream>

#include <algorithm>

using namespace std;

long long dp[201][201];

int main()

{

    int n, k;

    cin >> n >> k;

    int i;

    dp[0][0] = 1;

    for (int i = 1; i <= k; i++)

    {

        for (int j = 0; j <= n; j++)

        {

            for (int k = 0; k <= j; k++)

            {

                dp[i][j] += dp[i - 1][k];

                dp[i][j] %= 1000000000;

            }

        }

    }

    cout << dp[k][n] << "\n";

}

이렇게 된다!

 

근데 사실 표를 보면

n-1Sk + nSk-1 = nSk가 되는 것을 볼 수 있다

 

어..이건 중복조합에 대한 점화식인데???

 

사실 이 문제에 대한 답은 kHn이다

kHn이 무엇이냐면 중복조합인데 

 

nHr에 대해서 먼저 설명하자면

n개의 항목에 대해서 중복을 포함하여 r개를 택하는 중복 조합이다.

 

근데 왜 이 문제가 kHn인지 감이 잘 오지 않는 사람들도 있을 것이다.

 

nHr을 방금 뭐라고 하였는가? n개의 항목에 대해서 중복을 포함하여 r개를 택하는 것이라 했지 않았는가

 

사실 그렇다면 n개의 공을 r개의 상자에 나누는 방법과 같지 않을까?

 

공의 합은 n개 이고, 각각의 공들은 중복을 포함하여 r개의 상자에 들어갈 수 있는 것이다.

그렇다면 kHn에 대한 점화식에 대한 공식도 존재한다!

 

kHn= k-1Hn + kHn-1 이므로

 

이것을 이용하여 풀 수도 있다.