BOJ 2225 합분해

boj 2225 합분해

- 문제 링크

https://www.acmicpc.net/problem/2225

- 문제 해설

테이블 D[i][j]를 n이 i이고 k가 j일 때의 경우의 수라고 정의한다.
경우의 수를 어떻게 나눌지 잘 떠오르지 않아서 일단 n과 k에 따른 경우의 수를 작은 수부터 나열해보았다.

표로 나열해보면서 점화식을 유추해보자. 예를 들어 D[3][3]을 구한다고 해보자. 3을 3가지 수의 합으로 나타내는 경우는 0부터 3까지의 수를 2가지 수의 합으로 나타낸 것에다가 3이 되기위해 필요한 수를 더하면 된다.

• 0을 2가지 수의 합으로 나타낸 경우 : (0 + 0)
• 1을 2가지 수의 합으로 나타낸 경우 : (0 + 1), (1 + 0)
• 2를 2가지 수의 합으로 나타낸 경우 : (0 + 2), (1 + 1), (2 + 0)
• 3을 2가지 수의 합으로 나타낸 경우 : (0 + 3), (1 + 2), (2 + 1), (3 + 0)

• 3을 3가지 수의 합으로 나타낸 경우
  : 3을 3가지 수의 합으로 나타낸 경우는 위의 경우에서 3이 되기 위해 필요한 수를 동일한 위치에 더해주면 된다.
  3 + (0 + 0), 2 + (0 + 1), 2 + (1 + 0), 1 + (0 + 2), 1 + (1 + 1), 1 + (2 + 0), 0 + (0 + 3), 0 + (1 + 2), 0 + (2 + 1), 0 + (3 + 0)

그러므로, D[i][j] = D[0][j-1] + D[1][j-1] + ... + D{i-1][j-1] + D[i][j-1] 꼴인 것을 알 수 있다.
여기서 같은 방식으로 D[0][j-1] + D[1][j-1] + ... + D{i-1][j-1] = D[i-1][j] 이다.

그러므로, 점화식은 D[i][j] = D[i-1][j] + D[i][j-1] 이다.

- 코드 보기

#include <iostream>
#define mod 1000000000
using namespace std;

int n;
int k;
int D[205][205];

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

    cin >> n >> k;

    for (int i = 1; i <= k; i++) D[0][i] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            D[i][j] = (D[i - 1][j] + D[i][j - 1]) % mod;
        }
    }

    cout << D[n][k];
}