백준[2225]c++

문제 :

이 문제는 다이나믹 프로그래밍 통해 해결해야 하는 문제이다.

하나씩 생각을 해보자.

1부터 시작해보면... 열이 n이고 행을 k로 놨을 때 k가 1일 때 n을 만족하는 것은 무조건 자기 자신인 경우밖에 없기 때문에 1이다.

k가 2가 되면 n의 값보다 n+1개의 경우의 수가 발생한다.

한 번만 더 해보자.. k가 3이 되면 3,6,10,15이 되고, 써놓고 보니 점화식을 구할 수 있었다.

arr[i][j] = a[i-1][j] + a[i][j-1] 

위의 식을 그대로 구현해주기만 하면 이 문제는 간단하게 해결할 수 있다. (사실 파이썬으로 문제를 해결하고 C++로도 코드를 옮겨봤다.)

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

#include <iostream>
#include <vector>
#define MAX 201
typedef long long ll;
using namespace std;

int main() {
    int n, k,i;
    ll dp[MAX][MAX];

    cin >> n >> k;
    for (int i = 0; i < MAX; i++) {
        dp[1][i] = 1;
        dp[2][i] = i + 1;
    }
    for (int i = 2; i < MAX; i++) {
        dp[i][1] = i;
        for (int j = 2; j < MAX; j++) {
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
        }
    }
    cout << dp[k][n] << endl;
}