BOJ - 11401 이항 계수 3 해결 전략 (C++)

• 문제 링크
  백준 11401번 - 이항 계수 3

해결 전략

  본 문제는 상당히 난이도가 있는 문제로, 학부 이산 수학에서 배우는 개념들을 여럿 기억하고 있어야 해결할 수 있는 문제이다. 만약 인터넷 서칭이 불가능한 코딩 테스트에서 이러한 문제를 맞딱뜨린다면 해결이 쉽지 않을 수 있다.

  우선, 이항 계수 값을 구하는 일반적인 해결 방법은 이미 알다시피 대표적으로 다음의 두 가지가 있다.

1) Pascal's Identity를 이용해 Dynamic Programming 또는 Recursive하게 계산
2) Factorial을 이용해 Naive하게 계산

  이때, 1)번 방식은 굳이 Combination을 계산하지 않아도 알아서 계산되기 때문에 좋은 방법이라 학습한 바 있다. 하지만, 이 1)방식은 아무래도 중첩 반복문이나 스택 호출에 의존하기 때문에 입력으로 들어오는 수가 10000 이상이면 사실상 1초 내에는 계산이 힘들어진다.

  본 문제는 n이 4,000,000까지 입력이 가능하므로 1)방식은 폐기이다. 하지만, 그렇다고 해서 2)방식을 쉽게 적용할 수 있느냐? 그것도 아니다. 왜냐하면, 모듈라 연산의 성질 때문이다.

Modular 연산은 더하기나 곱하기에서는 분배가 가능하지만, 나눗셈에서는 분배할 수 없다.

  우리가 흔히 알고 있는 이항 계수 계산식은 팩토리얼 값들의 분수꼴이므로 손쉽게 모듈러 연산을 적용할 수가 없는 것이다.

  바로 이때 필요한 것이 앞서 언급한 '수학 지식'이다. '페르마의 소정리'라고 불리우는 정리인데, 그 내용은 아래와 같다.

이항계수 수식에서 분수 부분을 X라 할때, X^-1 % p를 X^(p-2)로 다루는 것이다.

  그렇다. 이 페르마의 소정리를 이용하면 수식을 아래와 같이 변형할 수 있는 것이다.

이때, 앞선 말한 'X 부분'에서 (n-k)!은 n!와 함께 묶어버리자. 그러면, 우리는 아래와 같은 수식으로 이 문제를 다룰 수 있다.

  이때, 우리는, '큰 수의 거듭제곱'이 필요하다. 이 부분은 Divide & Conquer 방식으로 해결할 수 있는데, 이전에 포스팅한 바 있는 백준 1629번 - 곱셈 문제의 해결 전략을 참고하자. a^m = a^(m/2) + a^(m/2)라는 간단한 원리를 이용하는 알고리즘이다.

  아래는 코드이다.

#include <iostream>
// BOJ - 11401 Binomial Coefficient 3
#define DIV		1000000007
using namespace std;

long long temp;

long long power(long long a, long long m) {
	if (m == 0) return 1;

	temp = power(a, m / 2) % DIV;
	if (m % 2 == 1) return temp * temp % DIV * a % DIV;
	return temp * temp % DIV;
}

void solve(int n, int k) {
	if (k == 1) { cout << n; return; }
	if (k == 0 || n == k) { cout << 1; return; }
	if (n - k == 1) { cout << n; return; }

	long long A = 1, B = 1, ans;
	for (int i = n; i >= n - k + 1; i--) A = (A * i) % DIV;
	for (int i = 1; i <= k; i++) B = (B * i) % DIV;
	ans = ((A % DIV) * power(B, DIV - 2) % DIV) % DIV;
	cout << ans;
}

int main(void) {
	int n, k;

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

	return 0;
}