[BOJ] 2225 합분해

주어진 문제에서 N과 K가 작을 때의 경우의 수를 각각 체크해보자.

0~N까지의 정수 K개를 더해 합이 N이 되는 경우의 수를 구해본다.

순서는 각 N에 대해 K가 증가하는 순서이다.

그런데, 이전 값과의 차이를 잘 보면...

N (합)	K (정수 갯수)	경우의 수	이전 값과의 차이 (K=1일 때부터 체크)
1	1	1 (1 자신)	0
1	2	2 (0+1, 1+0)	1
1	3	3 (0+0+1, 0+1+0, 1+0+0)	1
1	4	4 (0+0+0+1, 0+0+1+0 ......, 1+0+0+0)	1
......	......
2	1	1 (2 자신)	0
2	2	3 (02, 20, 11)	2
2	3	6 (002, 020, 200, 110, 011, 101)	3
2	4	10 (0002, 0020, 0200, ..... 1100, 0110, 0011, .....)	4
.......	.......
3	1	1 (3 자신)	0
3	2	4 (03, 30, 12, 21)	3
3	3	10 (003, 030, 300, 120, 012, 102, 210, 201....., 111)	6
3	4	20 (0003, 0030, 0300, 3000..... 0111)	10

여기서 F(N,K) 라는 함수를 위 문제에서 구하는 경우의 수라고 했을 때,

F(2,2) 는 F(2,1) + F(1,2)와 같고,

F(2,4) 는 F(2,3) + F(1,4)와 같다.

또 F(3,3)은 F(3,2) + F(2,3)과 같다.

즉, 일정한 규칙이 있음을 알 수 있었고 이를 점화식으로 옮겨보았다.

F(N,K) = F(N, K-1) + F(N-1, K) (단, N >=2, K >=2 일 때)

경우의 수를 구할 때 이전에 구하여 저장한 경우의 수를 가져온다.

경우의 수를 구할 때마다 캐시에 저장해놓고 다음 경우의 수 구할 때 활용하면 되는 형태인 것이다.

또한, N=1일 때 경우의 수는 K와 같다.

0이 K-1개, 1이 1개 쓰이기 때문에 K=5면 10000, 01000, 00100... 이런 식의 조합으로 구할 수 있기 때문이다.

결국, 이 문제는

메모이제이션을 통한 다이나믹 프로그래밍 문제인 것이다.

위에서 구한 걸 코드로 옮겨 보았다. (실제 AC받은 코드)

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <string>
#include <random>
#include <string.h> //gcc memset
#include <math.h>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N = 0, K = 0;
    cin >> N >> K;
 
    int DP[202][202]; //DP[a][b] : 정수 b개를 더해서 합이 a가 되는 경우의 수
    memset(DP, 0, sizeof(DP));
 
    int x = 0, y = 0;
    //K개로 1을 만드는 가짓수는 K개이다 (0을 K-1개, 1을 1개 사용)
    for (x = 1; x <= K; ++x)
        DP[1][x] = x;
 
    //정수 y개를 더해 x를 만드는 경우의 수를 구한다. (N,K값이 작을 때 손으로 직접 규칙을 찾아봄)
    //y=1일 경우 당연 1가지만 존재
    //y>=2일 경우 (y-1개로 x를 만드는 가짓수) + (y개로 x-1을 만드는 가짓수)
    for(x = 2; x <= N; ++x)
        for (y = 1; y <= K; ++y)
        {
            if (y == 1)
                DP[x][y] = 1;
            else
                DP[x][y] = (DP[x][y - 1] + DP[x - 1][y]) % 1000000000;
        }
 
    cout << (DP[N][K] % 1000000000) << "\n";
    return 0;
}