[알고리즘] 백준 11051번: 이항 계수 2 (C++)

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

11051번: 이항 계수 2

 

이항 계수 n r이 nCr이라는 것을 알면 예전에 풀었던 문제와 똑같이 풀린다.

다른 점은 나머지 정리(MOD == 10007)로 인해 문자열의 합을 구할 필요 없다는 점이었다.

(콤비네이션 예전 포스팅 https://draw-code-boy.tistory.com/101)

 

[AC 코드]

#include <iostream>
#include <cmath>
#define MOD 10007
using namespace std;

int cache[1001][1001];

int combi(int n, int r) {
	if (n == r || r == 0) {
		return 1;
	}
	else {
		if (cache[n][r]) {
			return cache[n][r];
		}
		else {
			return cache[n][r] = (combi(n - 1, r - 1) + combi(n - 1, r)) % MOD;
		}
	}
}

int main() {
	int n, k;
	cin >> n >> k;
	cout << combi(n, k);
	return 0;
}