BOJ - 11051 이항 계수 2 해결 전략 (C++)

• 문제 링크
  백준 11051번 - 이항 계수 2

해결 전략

  대부분의 대학교 학부 컴퓨터공학과 1학년 과정에서는 이산 수학, 이산 구조, Discrete Structure에 대해 학습한다. 본인 역시 해당 과목을 수강하였다. 수강 과정에서 매우매우 자주 사용하였던 공식이 하나 있는데, 그 공식이 바로 'Pascal's Identity'라고 불리는 이항 계수 항등식이다.

C(n, k) = C(n - 1, k) + C(n - 1, k - 1)

  이 공식은 이항 계수 Combination을 설명하는 'Pascal's Triangle'에서 도출하였음을 배운 바 있다.

  본 문제는 바로 이 공식을 알고 있다면 매우 쉽게 해결할 수 있는 문제이다. 굳이 알고리즘을 범주화하자면 Dynamic Programming일 것이다. 더 이상의 설명은 불필요할 것이다. 아래는 정답 코드이다.

#include <iostream>
// BOJ - 11051 Binomial Coefficient 2
using namespace std;
#define DIV  10007
int c[1001][1001];	// nCk = n-1Ck-1 + n-1Ck

void make_combination(int n, int k) { 
	for (int i = 1; i <= n; i++) { c[i][0] = 1; c[i][i] = 1; }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++)
			c[i][j] = (c[i - 1][j - 1] % DIV + c[i - 1][j] % DIV) % DIV;
	}
	cout << c[n][k];
}

int main(void) {
	int n, k;

	cin >> n >> k;
	make_combination(n , k);

	return 0;
}