[백준/C++] 11050번 : 이항 계수 1 (조합, 팩토리얼, 이항계수 공식)

이항 계수 1

문제

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

입력

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

출력

 이항계수(N/K)를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

---

📌이항계수 (Binomial Coefficient)

이항계수란 조합론에서 등장하는 개념으로, 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑을 수 있는 조합의 가짓수를 말한다. 

평소 알고있던 nCk 를 말하는 것이다!

 

2를 상징하는 '이항'이라는 단어가 붙은 이유는 '뽑거나, 안뽑거나'의 두 가지 선택지가 존재하기 때문이다.

 

전체 집합에서 원소의 개수 n에 대해 k개의 아이템을 뽑는 이항계수(조합의 수)는 아래와 같은 공식을 갖는다.

 

해당 공식을 바탕으로 문제를 풀이해보았다.

 

#include <iostream>
#include <string>

using namespace std;

int Factorial(int n)
{
	if (n == 0)
		return 1;
	if (n > 2)
		n *= Factorial(n - 1);
	return n;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, K;
	cin >> N >> K;

	cout << Factorial(N) / (Factorial(N - K) * Factorial(K));

	return 0;
}

 

알던대로 팩토리얼 함수를 작성하여 공식대로 사용하면 되고, 

이때 한가지 주의할 점은 K의 값이 0도 들어갈 수 있으므로 Factorial 0! = 1 이라는 처리를 해주어야 한다.

---

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

11050번: 이항 계수 1

https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

[조합론] 이항계수 알고리즘 3가지