백준 합분해 [c++]

2225 합분해 골드5

문제

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

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

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

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

풀이

• 이전에 풀었던 카드 구매하기(11052)문제와 동일한 dp문제.
• k가 증가할수록 i~(n+1)까지의 합을 i가 0에서 n+1까지 증가해가며 합하는 dp식이 나옴.
• 마찬가지로 모듈러 연산을 할때 부분합을 구하는 부분에서도 모듈러를 써줘야 제한 수 범위를 넘지 않는다.

코드

#include <iostream>
using namespace std;

int main(){

    int n, k;
    cin >> n >> k;
    int dp[n+1];

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

    if(k == 1){
        cout << 1 << endl;
        return 0;
    } else if(k == 2)
    {
        cout << n+1 << endl;
        return 0;
    }

    for(int kth = 3; kth <= k; kth++)
    {
        for(int d = 0; d <= n; d++)
        {
            int sum = 0;
            for(int s = d; s <= n; s++)
            {
                sum = (sum + dp[s]) % 1000000000;
            }
            dp[d] = sum % 1000000000;
        }

        // for(int i = 0; i <= n; i++)
        // {
        //     printf("%10d", dp[i]);
        // }
        // cout << endl;
    }

    int result = 0;
    for(int i = 0; i <= n; i++)
    {
        result = (result + dp[i]) % 1000000000;
    }

    cout << result % 1000000000 << endl;

    return 0;
}

• ps
• dp