[BOJ] 2225. 합분해

2225. 합분해

1. 문제

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

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

2. 입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

3. 출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

4. 풀이

C++

#include <iostream>
using namespace std;
#define ioboost ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MAX 1000000000

int N, K;
int dp[201][201];
// dp[i][j] = k : 0부터 i까지의 정수 j개를 더해서 그 합이 i이 되는 경우의 수가 k개

void Solve()
{
    for (int i = 1; i <= K; ++i)
    {
        for (int j = 0; j <= N; ++j)
        {
            for (int k = 0; k <= j; ++k)
                dp[j][i] = (dp[j][i] + dp[k][i - 1]) % MAX;
        }
    }
    
    cout << dp[N][K] << '\n';
}


int main()
{
    ioboost;
    cin >> N >> K;
    for (int i = 0; i <= N; ++i)
        dp[i][1] = 1;
    
    Solve();
    
    return 0;
}