[백준][C++] 11051: 이항 계수 2

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

 

dp와 모듈러 연산을 적절히 사용하면 됩니다

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;

int dp[1001][1001];

int bino(int n, int k) {
	if (n == k || k == 0) return 1;

	auto& ret = dp[n][k];
	if (ret != -1) return ret;

	return ret = (bino(n-1, k-1)%MOD + bino(n-1, k)%MOD)%MOD;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	memset(dp, -1, sizeof(dp));

	int n, k;
	cin >> n >> k;
	cout << bino(n, k) << '\n';
	
	return 0;
}