[백준 2225번] 합분해 (C++)

문제링크 : https://www.acmicpc.net/problem/2225

2225번: 합분해

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K;
const int MOD = 1000000000;
int dp[201][201];

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

    cin >> N >> K;
    for(int i=0; i<N; i++) dp[i][0] = 1; //첫 세로줄 초기화
    for(int i=0; i<K; i++) dp[0][i] = i+1; //첫 가로줄 초기화

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

DP 문제이다. 

처음 경우의 수를 확인하여 규칙을 찾아보았다.

N/K 1 2 3  4  5
 1  1 2 3  4  5
 2  1 3 6  10 15
 3  1 4 10 20 35
 4  1 5 15 35 70
 5  1 6 21 56 126

첫 세로줄을 먼저 살펴보면 K = 1이기에 N이 어떤 수가 오든 간에 1 밖에 못오므로 1로 고정인 것을 알 수 있다.

그리고 가로줄을 살펴보면 합이 1이므로 K가 늘어남에 따라 0만 하나씩 추가되어 K와 경우의 수가 같은 것을 알 수 있다.

(01, 10 / 001, 010, 100 / 0001, 0010, 0100, 1000 ...)

이후로 오는 수들은 dp[i][j] = dp[i-1][j] + dp[i][j-1]임을 위에 작성한 표를 통해 알 수 있다.