[Baekjoon/C++] 11050번 - 이항 계수 1

Baekjoon Online Judge

문제로 이동

 

문제

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

 

입력

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

 

출력

 (NK)를 출력한다.

 

---

예제 입력	예제 출력
5 2	10

---

풀이

#include <iostream>
using namespace std;

int arr[11] = { 1, 1 }; // 팩토리얼을 저장한다.

// 팩토리얼 함수
int factorial(int n) {
	if (arr[n] == 0)
		return arr[n] = n * factorial(n - 1);
	else
		return arr[n];
}

int main() {
	int N, K;
	cin >> N >> K;

	// 출력
	printf("%d", factorial(N) / (factorial(K) * factorial(N - K)));

	return 0;
}

이항 계수 공식 : (N K) = N! / (K! * (N - K)!)

팩토리얼 함수를 구현해서 이항계수를 풀었다. 이미 구했던 팩토리얼을 또 구하면 비효율적이기 때문에 배열을 하나 만들어서 팩토리얼을 저장하고, 필요하다면 여기서 꺼내오도록 했다.