[백준] 2225

합분해

문제

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

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

입력

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

출력

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

풀이

#include <iostream>

int dp[201][201]; // n, k

int main(void) {
    int n, k;

    std::cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (i == 1) dp[i][j] = j;
            else if (j == 1) dp[i][j] = 1;
            else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
        }
    }

    std::cout << dp[n][k];
}

반성회

n = 1, k = 1

1

n = 1 k = 2

0 1
1 0

n = 1 k = 3

0 0 1
0 1 0
1 0 0

n = 1 k = 4

0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

n = 2, k = 1

2

n = 2, k = 2

0 2
1 1
2 0

n = 2, k = 3

0 0 2
0 2 0
2 0 0
0 1 1
1 0 1
1 1 0

n = 2, k = 4

0 0 0 2
0 0 2 0
0 2 0 0
2 0 0 0
0 0 1 1
0 1 0 1
1 0 0 1
0 1 1 0
1 0 1 0
1 1 0 0

첫 번째 인덱스가 1부터 n까지의 i이고

두 번째 인덱스가 1부터 k까지의 j라고 했을 때

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 이라는 식이 나온다

규칙을 찾아서 풀..긴 했는데 이렇게 풀어도 되는걸까 🤷