백준 2225번: 합분해

백준 2225번: 합분해

2225번: 합분해

DP문제는 규칙을 먼저찾는게 우선이라고 생각한다. 규칙을 찾기위해서 수를 종이위에 어느정도 써본 결과 일정한 규칙이 있다는 사실을 알아냈다. dp[n][k]의 값은 dp[0][k-1] + dp[1][k-1] + ... + dp[n][k-1] 의 값을 가진다는 것을 알아내었다. 따라서 n이 0일때의 값만 1로 초기화를 해준 뒤 이후의 값들은 공식을 코드로 구현하여 해결했다.

마지막에 1,000,000,000을 나누는 것을 잊지말자

 

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 0; i <= n; i++)
    {
        dp[i][1] = 1;
    }
    for(int i = 2; i <= k; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            for(int z = 0; z <= j; z++)
            {
                dp[j][i] = (dp[j][i] + dp[z][i-1])%DIV;
            }
        }
    }
    cout << dp[n][k];
    
    return 0;
}