[c++] 백준 11050, 11051 이항계수 1, 이항계수 2

백준 단계별로 풀어보기 [정수론 및 집합론] 이항계수 1

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

11050번: 이항 계수 1

 

[풀이]

이항계수 1 - factorial 함수를 재귀를 이용하여 구현. n, k의 이항계수는 nCk = n! / (n-k)!k! 이다.

이항계수 2 - 동적계획법을 이용해서 구현. 이항계수를 점화식으로 표현하면 다음과 같다.

이항계수 점화식

[코드]

-이항계수 1

#include<iostream>

int factorial(int n) {
	if (n == 0) return 1;
	else {
		return n * factorial(n - 1);
	}
}

int main() {
	int n, k;
	std::cin >> n >> k;
	std::cout << factorial(n)/(factorial(n-k)*factorial(k));
}

-이항계수 2(동적계획법)

#include<iostream>

int bc[1001][1001];

int main() {
	int n, k;
	std::cin >> n >> k;
	bc[0][0] = 1;
	bc[1][0] = 1;
	bc[1][1] = 1;

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || i==j)
				bc[i][j] = 1;
			else {
				bc[i][j] = (bc[i - 1][j - 1] + bc[i - 1][j]) % 10007;
			}
		}
	}

	std::cout << bc[n][k];
}