백준 2225 - 합분해

문제 설명

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, K개의 수를 이용하여 N을 만드는 경우의 수를 구하는 문제이다.

 

문제를 푸는 방법은 간단하다.

1개부터 K개까지의 수를 이용하여 N을 만든다고 생각하는 것이다.

예를 들어, 20(N)을 2(K)개의 수로 만드는 상황을 보자.

 

그렇다면 1개의 수로 20을 만드는 방법은 1개밖에 없다.

그럼 2개의 수로 20을 만드는 방법은 다음과 같다.

{0, 20}, {1, 19}, {2, 18}, {3, 17} ....

즉, K-1개로 a라는 수를 만들고 거기에 N-a를 더하면 K개로 N을 만드는 것이 된다.

따라서, 1~K개를 이용하여 N을 만드는 방법은 다음과 같다.

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

1개로 N을 만드는 것은 모두 1개밖에 없기 때문에 다음과 같이 초기화해야 한다.

for (int i = 0; i <= N; i++)
{
    dp[1][i] = 1;
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, K;
const int DIV = 1'000'000'000;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;
    vector<vector<long long>> dp(K + 1, vector<long long>(N + 1, 0));

    for (int i = 0; i <= N; i++)
    {
        dp[1][i] = 1;
    }

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

    cout << dp[K][N];

    return 0;
}

---