백준 13707 합분해 2

문제 링크 : https://www.acmicpc.net/problem/13707
풀이 :

#include <iostream>
using namespace std;

int arr[5001][5001];

// arr[i][j] = arr[i-1][j] + arr[i][j-1]
// k = 1 -> 1 way
// n = 0 -> 0 way

int dp(int n, int k) {
	if (k == 1) return 1;
	if (n == 0) return 1;
	if (arr[n][k] != 0) return arr[n][k];
	return arr[n][k] = (dp(n - 1, k) + dp(n, k - 1)) % 1000000000;
}

int main() {
	int n, k;
	cin >> n >> k;

	cout << dp(n, k);
}

흔한 DP문제 중 하나였다.
% 1000000000 를 해주는것만 빼먹지 않으면 된다.