BOJ : 2225 합분해

---

[BOJ 2225(G5) 리뷰]

이 문제는 처음에 규칙이 잘 보이지 않았다.

일단 고려해야 할 점은 0을 더할 수 있다는것이다.

나는 집적 경우의 수를 나열하며 규칙을 찾았다.

 

각 행은 정수 K를 나타내고 각 열은 N까지의 경우의 수를 나타낸다.

예를들어 N=3,K=2라면 0,1,2,3중 숫자 2개를 사용하여 3을 나타내는 경우의 수 이다.

이때의 경우의 수는 0+3, 3+0 ,1+2 ,2+1 로 총 4개이다.

 

여기서 만약 K가 3이라면 어떻게 될까?

맨앞이 0이고 나머지 숫자 2개를 이용하여 3을 나타내는 경우의 수 +

맨앞이 1이고 나머지 숫자 2개를 이용하여 2를 나타내는 경우의 수 +

맨앞이 2이고 나머지 숫자 2개를 이용하여 1을 나타내는 경우의 수 +

맨앞이 3이고 나머지 숫자 2개를 이용하여 0을 나타내는 경우의 수 이다.

 

따라서 DP[3][3]=DP[2][0]+DP[2][1]+DP[2][2]+DP[2][3]이 된다.

위 규칙을 이해하고 표를보면 이해가 쉬울것이다.

	0	1	2	3	4
1	1	1	1	1	1
2	1	2	3	4	5
3	1	3	6	10	15

 

 

이걸 그대로 코드로 구현하면 된다. 문제에서 알려준대로 10억으로 나눠주는걸 잊지말자.

---

#include <bits/stdc++.h>
using namespace std;
int dp[201][201] = { 0, };
int N,K;


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

    cin >> N >> K;
    
    for (int i = 1; i <= K; i++)
        dp[i][0] = 1;

    for (int i = 0; i <= N; i++)
        dp[1][i] = 1;

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

    cout << dp[K][N];
}