백준 11050 이항 계수 1 C++

문제

자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 10, 0 ≤ K\(K\) ≤ N\(N\))

출력

(NK)\(\binom{N}{K}\)를 출력한다.

 

내 풀이

조합론에서 이항 계수(binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는)조합의 가짓수이다.

이항계수 알고리즘에는 다양한 종류가 있지만

이번 문제에서는

nCk = n-1Ck-1 + n-1Ck ( n >= k ,n >= 2, k >= 1)라는 성질을 이용하여 풀어보았다.

 

#include<iostream>
using namespace std;

int binomial(int n, int k) {
	if (n < k) return 0;
	if((n == 1)||(k == 0)) return 1;
	return binomial(n - 1, k - 1) + binomial(n - 1, k);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;

	cin >> n >> k;

	cout << binomial(n, k) << '\n';

	return 0;
}