[BOJ] 합분해 2225번 C++

문제

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

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

입력

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

출력

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

 

접근 방식

 

먼저, dp 배열을

dp[N][K] = N을 K개의 숫자로 만드는 경우의 수로 정의한다

이때 dp[i][j]가 되는 경우를 두 가지로 나눌 수 있다.

1. j개의 숫자를 사용해서 i를 만들 때 마지막 숫자가 0인 경우 =>  남은 j-1개로 i를 만들어야 하기 때문에  dp[i][j-1]를 그대로 가져옴

2. j개의 숫자를 사용해서 i를 만들 때 마지막 숫자가 1이상인 경우 => (i-1)을 j개로 만드는 경우에 +1을 추가하면 되기 때문에 dp[i-1][j]를 더해주면 된다

 

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1000000000;
int dp[202][202]; // dp[i][j]: i를 j개의 숫자로 만드는 경우의 수

int main() {
    int N, K;
    cin >> N >> K;

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

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

    cout << dp[N][K] << '\n';

}