[알고리즘 문제] 백준2225 - 합분해

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

2225번: 합분해

이 문제는 2차월 배열을 사용한다. dp문제를 풀다보면 대부분 1차원 또는 2차원 배열 중 하나를 사용하는 것 같다. 이 문제에서 사용하는  2차원 배열의 정의를 보자.

 

dp[a][b]=c  : a개를 더해서 그 합이 b인 경우의 수 c

 

그리고 문제를 해결하는데 있어 중요한 개념을 먼저 설명하면, [1,2,3,4]의 순열의 개수는 4!이다. 만약 천의 자리가 1인 순열의 개수는 (4-1)!이다. 이는 1이 천의 자리에 고정되어 있으며 남은 3개의 숫자로 순열의 개수와 같다. 만약 천의 2자리가 2인 순열의 개수는 ? 마찬가지로 (4-1)!이다. 그럼 3은? 4는? 각각의 경우 모두 3!의 경우를 가진다. "이 각각의 경우는 모두 1,2,3,4" 이기 때문에 3! * 4를 하면 4!가 된다.

다시 문제로 돌아가서, 20을 3번의 합으로 구할 수 있는 경우의 수는 어떻게 구할 수 있을까 ? 정답부터 말하면 0 ~ 20을 2번의 합으로 구할 수 있는 경우의 수를 모두 더하면 된다.

 

이게 무슨말일까 ?? 이해가 안되지만 논리적으로 그렇게 돌아간다. 왜 그런지 설명하면, 

3번을 더해야 하는데 2번을 더한다는 말은 1개의 자리가 비었다는 의미이다. 여기서 이 1개의 자리가 위에서 설명한 "1이 천의 자리에 고정된 경우"와 같다. 

 

그리고 0 ~ 20인 경우 2번으로 만들 수 있는 경우를 모두 더해주는 이유는, 위의 천의 자리에 각각 1,2,3,4가 올 수 있는 숫자가 다르기 때문이라는 이유와 비슷하다. 이를 점화식으로 풀어보면 다음과 같다.

 

dp[3][20] = dp[2][0] + dp[2][1] + ..... + dp[2][19] + dp[2][20] 

 

위에서 dp[2][0] ~ dp[2][20]의 값을 모두 더한 이유는 간단하다. 위의 순열에서 천의 자리가 "고정" 되어 있다고 가정했을 때의 경우의 수는 3!인데, 천의 자리에올 수 있는 숫자가 4개 이기 때문에 3! + 3! +3! +3!한 이유와 같다. 

 

즉 dp[2][x]에 하나의 숫자를 추가함으로 써 우리는 이 값이 20으로 만들 수 있다. 하지만 이런 경우가 0 ~ 20이 있기 때문이다. 단적인 예로, 1 ~ 19 = 20, 2 ~ 18 = 20, 3 ~ 17 = 20...이런 것처럼

 

#include <iostream>

using namespace std;

int main()
{

    int N, K;
    cin >> N >> K;
    long long dp[201][201] = {0};

    int mod = 1000000000;

    for (int i = 0; i <= N; i++)
    {
        dp[1][i] = 1; // 1개 더해서 그 값이 b인 경우는 무조건 하나임
    }

    // dp[a][b] = c 의 의미는 "a개 더해서 그 합이 b가 되는 경우의 수는 c개 입니다." 이다.

    for (int i = 2; i <= K; i++)
    {
        for (int j = 0; j <= N; j++)
        {
            for (int l = 0; l <= j; l++)
            {
                dp[i][j] += dp[i - 1][j - l];
            }
            dp[i][j] %= mod;
        }
    }

    for (int i = 0; i <= N; i++)
    {
        for (int h = 0; h <= N; h++)
        {
            cout << dp[i][h] << " ";
        }
        cout << "\n";
    }

    cout << dp[K][N];

    return 0;
}