백준 2225 합분해 c++ // dp 규칙찾는 방법

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

2225번: 합분해

1. dp 규칙찾는 방법

1.1 표를그린다

1.2 규칙을세우고(뒤에만 숫자추가하기) 경우의수를 센다.

1.3. 그 숫자가 어디서 왔는지 규칙을 찾고 화살표로 표시한다

1.4. 규칙을 찾았으면 dp 테이블로 옮기고 숫자의 이동을 표시한다.

1.5. 점화식을 세운다(dp[j]=dp[j]+dp[j-1])

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int n, k;
int dp[204];
int divd = 1000000000;

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

    cin >> n >> k;

    fill(dp, dp + 204, 1);

    for (int i = 2; i <= k; ++i) { //회차
        for (int j = 1; j <= n; ++j) {
            dp[j] = dp[j]%divd + dp[j - 1]%divd;
            //cout << dp[j] << " ";
        }
    }

    //for (int i = 0; i <= n; ++i) cout << dp[i] << " ";
    cout << dp[n] % divd;

    return 0;
}