문제 링크: 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;
}
반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 5462: POI  (0) 2020.08.07
[백준][C++] 5463: 건포도  (0) 2020.08.06
[백준][C++] 11003: 최솟값 찾기  (0) 2020.08.04
[백준][C++] 5893: 17배  (0) 2020.08.03
[백준][C++] 4485: 녹색 옷 입은 애가 젤다지?  (0) 2020.08.03