[ 백준 2225 ] 합분해 (C++)

백준의 합분해(2225) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 0 ~ N까지의 숫자 중에서 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.

   그렇다면 작은 숫자부터 어떻게 풀어나가야 할지 알아보자.

   먼저 본인은 이 경우의 수를 저장하기 위해서 DP[][] 2차원 배열을 사용하였다.

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

   즉, 우리가 구해야 할 결과값은 DP[K][N]의 값이다.

   그렇다면 DP[1][N] 의 값은 얼마일까 ?? N이 무슨 값이든 상관없이 DP[1][N]의 결과는 1이다.

   어떤 수를 한 개만 더해서 N이 나오는 경우의 수는 N값 그 자신 하나밖에 없기 때문이다.

  

   위의 식은 초기설정 값이라고 볼 수 있다.

   또한, K가 0일 경우 DP[K][x] = 0 이라고 볼 수 있다. 어떤 수를 0개를 더해서 합이 x가 되는 경우는 없기 때문에 0이다.

  

   그렇다면 , 2개를 더해서 2가 나오는 경우의 수에 대해서 알아보자.

   K = 2 , N = 2 인 경우이다.

   (0 + 2) , (1 + 1), (2 + 0) 이렇게 총 3개의 경우가 있을 것이다.

   조금 더 식을 구체적으로 써보자면

   0 + 2 = (한개를 더해서 0이 나오는 경우) + (한개를 더해서 2가 나오는 경우)

   1 + 1 = (한개를 더해서 1이 나오는 경우) + (한개를 더해서 1이 나오는 경우)

   2 + 0 = (한개를 더해서 2가 나오는 경우) + (한개를 더해서 0이 나오는 경우)

   위의 과정처럼 0부터 N까지 진행을 한다고 생각해보면 점화식은

   DP[K][N] = DP[K-1][0] + DP[K-1][1] + ... + DP[K-1][N]이 된다.

   또한 연산결과를 Moduler값으로 나눠줘야 한다는 점에 주의하고, DP배열의 값 자체도 long long 으로 바꿔줘야지만

   맞았습니다를 받을 수 있다.

[ 소스코드 ]

#include<iostream>
 
typedef long long ll;
#define endl "\n"
#define MAX 201
#define Moduler 1000000000
using namespace std;
 
int N, K;
ll DP[MAX][MAX];
    
void Input()
{
    cin >> N >> K;
}
 
void Solution()
{
    for (int i = 0; i <= N; i++)
    {
        DP[1][i] = 1;
    }
 
    for (int k = 2; k <= K; k++)
    {
        for (int n = 0; n <= N; n++)
        {
            for (int i = 0; i <= n; i++)
            {
                DP[k][n] = DP[k][n] + DP[k - 1][i];
            }
            DP[k][n] = DP[k][n] % Moduler;
        }
    }
 
    cout << DP[K][N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}