[BOJ] 2225 : 합분해

문제 링크

2225번: 합분해 (acmicpc.net)

2225번: 합분해

DP를 이용해서 숫자 N을 K개의 숫자 조합으로 만드는 경우의 수를 출력하는 문제.

 

풀이

DP[N][K] 배열을 만들어서 DP[Y][X] 에는 숫자 Y를 숫자 X개를 조합해서 만드는 경우의 수를 저장해야겠구나 생각했다.

일단 Bottom-up 방식으로 DP[0][1], DP[1][1], ... , DP[N][1], DP[0][2], DP[1][2], ... , DP[N][K] 이렇게 채워나가야겠다고 생각은 했지만, 점화식을 어떻게 해야할 지가 관건이다.

처음에는 예를 들어 DP[3][3]을 채우기 위해서는 DP[0][1] * DP[3][2] + DP[0][2] * DP[3][1] + DP[1][1] * DP[2][2] + DP[2][1] * DP[1][2] + DP[2][2] * DP[1][1] + DP[3][1] * DP[0][2] + DP[3][2] * DP[0][0] 이렇게 모든 조합의 경우의 수를 고려해야 한다고 생각했다.

이게 무슨 의미냐면 3이라는 숫자는 0 + 3, 1 + 2, 2 + 1, 3 + 0 처럼 2개의 수의 덧셈으로 표현가능한데 K개의 숫자를 사용해야 하므로 각 2개의 수를 만드는 숫자의 개수의 합이 K개가 되면 된다는 것이다.

1 + 2 의 상황을 봤을 때 1을 1개의 숫자를 조합해서 만들었다면 2는 2개의 숫자를 조합해서 만들어야 3은 3개의 숫자를 조합해서 나왔다고 할 수 있다. 그래서 앞의 점화식을 생각하게 됐는데 저렇게 했을 때는 문제가 발생한다.

더하는 순서가 다르면 다른 조합이라고 했기 때문데 순서를 고려해서 DP[2][2] * DP[1][1], DP[1][1] * DP[2][2] 을 모두 더해주었다.

DP[2][2] * DP[1][1] 은 2를 2가지 숫자를 조합해 만들고 1을 1가지 숫자로 조합해 만든다는 뜻인데

{(0,2), (1,1), (2,0)} * {1} 의 경우이다 0 + 2 + 1, 1 + 1 + 1, 2 + 0 + 1 이렇게 3가지가 나온다.

DP[1][1] * DP[2][2] 은 순섭만 바꾼 경우인데 

{1} * {(0,2), (1,1), (2,0)} 의 경우이므로 1 + 0 + 2, 1 + 1 + 1, 1 + 2 + 0 이렇게 3가지가 된다.

이렇게 되면 1+ 1 + 1의 경우가 중복되는 현상이 발생한다. 모든 상황에서 중복되는 조합을 찾아 빼주는 것은 무리이다. 그래서 조합을 다시 한 번 봤다.

3을 3가지 숫자로 조합하는 방법을 모두 구해보자.

3 + 0 + 0     1 + 1 + 1    1 + 0 + 2    0 + 0 + 3

0 + 3 + 0     2 + 0 + 1    0 + 1 + 2

1 + 2 + 0     0 + 2 + 1

2 + 1 + 0

이렇게 총 10가지의 경우가 있다.

빨간색 부분을 잘보면 각각 DP[3][2], DP[2][2], DP[1][2], DP[0][2] 인 것을 알 수 있다.

여기서 우리는 점화식을 찾아낼 수 있다.

DP[N][K] = DP[0][K-1] * DP[N][1] + DP[1][K-1] * DP[N-1][1] + ... + DP[N][K-1] * DP[0][1].

그런데 DP[X][1] 의 값은 X 값에 상관없이 모두 1이므로 생략 가능하다.

DP[N][K] = DP[0][K-1] + DP[1][K-1] + ... + DP[N][K-1] 이라는 것을 알 수 있다.

이 점화식을 사용해서 풀면 정답이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 200 + 5;
int N, K;
ll DP[MAX_N][MAX_N];
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    DP[0][0] = 1;
    for (int i = 0; i <= N; i++) {
        DP[i][1] = 1;
    }
    for (int i = 2; i <= K; i++) {
        for (int j = 0; j <= N; j++) {
            for (int p = 0; p <= j; p++) {
                DP[j][i] += DP[p][i - 1];
            }
            DP[j][i] %= 1000000000;
        }
    }
    cout << DP[N][K] << "\n";
    return 0;
}