BOJ 11439: 이항 계수 5

올해들어 알고리즘 공부를 뜸하게 하다가 최근 일주일에 몇 문제씩은 풀게되었다.

 

이항 계수 4 문제까지는 구글링을 통해 다양한 공식과 정리들을 알게되어 쉽게 해결하였지만 최근 도전했던 이항 계수 5는 도저히 어떠한 공식도 정리도 찾을수가 없었다.

 

내가 이 문제를 풀기 위해 어떤 방식으로 접근했는지와 결국 풀이를 떠올리고 풀어낸 방법을 소개하고자 한다.

 

1. 먼저 N제한이 400만이기 때문에 DP를 사용하기에는 너무나도 큰 메모리 공간이 필요하기 때문에, 아마 메모리 공간이 부족하지 않더라도 너무나도 긴 시간이 걸릴 것이기 때문에 불가능하다고 생각했다.

 

2. 이항 계수 4를 풀기 위해 사용했던 Lucas Theorem을 사용해보고자 했지만 나누는 수가 소수인 경우에만 사용할 수 있으므로 포기했다.

 

3. 그렇다면 그냥 팩토리얼을 계산하여 모듈러 역원을 구해 답을 구해보고자 했다.

 3-1. 먼저 Fermat's little theorem을 이용하여 모듈러 역원을 구해보자 했지만 두 수가 서로소가 아닌 경우가 있어 포기했다.

 3-2. Euler phi function을 이용하여 모듈러 역원을 구해보자 했지만 팩토리얼을 계산할 때 수가 0이 되어버리는 경우가 있어 포기했다.

 

4. 아마 이때 가장 많은 삽질을 한 것 같다. 이항 계수와 관련된 공식과 정리들을 모두 써놓고 새로운 방법이 없는지 많은 고민을 했다. 특히 파스칼 삼각형을 그려놓고 쉽게 구할 수 있는 방법이 없을까 많은 고민을 했다.

 

5. 1-2시간 정도를 고민하다가 맥주를 마신 덕분인지 조합 0의 개수라는 문제가 떠올랐다. 그래서 nCr의 결과를 소인수분해 해보기로 마음먹었다. 이 방법을 통해 맞았습니다를 받았다.

 

소스코드가 포함된 풀이는 아래에서 볼 수 있다.

먼저 소인수분해를 하기 위해 N이하의 소수를 에라토스테네스의 체를 이용하여 구했다.

bool sieve[4040404] = { 1, 1 };
for (int i = 2; i * i <= n; ++i) {
		if (sieve[i]) continue;
		for (int j = i * i; j <= n; j += i)
			sieve[j] = 1;
	}
vector<ll> p;
for (int i = 2; i <= n; ++i)
	if (!sieve[i]) p.push_back(i);

 

그리고 해당 소수가 nCr에 몇 개나 들어있는지 세어주기 위한 배열을 만들고

vector<ll> cnt(p.size());

 

n!에 들어있는 해당 소수의 개수를 세어주며, r!, (n-r)!에 들어있는 해당 소수의 개수만큼을 빼주는 작업을 했다.

for (int i = 0; i < p.size(); ++i)
	for (ll j = p[i]; j <= n; j *= p[i])
		cnt[i] += ((n / j) - (r / j) - ((n - r) / j));

 

이후에는 모듈러 연산자의 성질과 소인수분해 결과를 이용하여 답을 구했다.

ll res = 1;
for (int i = 0; i < cnt.size(); ++i) {
	for (int j = 0; j < cnt[i]; ++j) {
		res *= p[i];
		res %= m;
		if (res == 0) {
			printf("0"); return 0;
		}
	}
}

전체 코드는 다음과 같다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool sieve[4040404] = { 1, 1 };
int main() {
	ll n, r, m; scanf("%lld %lld %lld", &n, &r, &m);
	for (int i = 2; i * i <= n; ++i) {
		if (sieve[i]) continue;
		for (int j = i * i; j <= n; j += i)
			sieve[j] = 1;
	}
	vector<ll> p;
	for (int i = 2; i <= n; ++i)
		if (!sieve[i]) p.push_back(i);
	vector<ll> cnt(p.size());
	for (int i = 0; i < p.size(); ++i)
		for (ll j = p[i]; j <= n; j *= p[i])
			cnt[i] += ((n / j) - (r / j) - ((n - r) / j));
    
	ll res = 1;
	for (int i = 0; i < cnt.size(); ++i) {
		for (int j = 0; j < cnt[i]; ++j) {
			res *= p[i];
			res %= m;
			if (res == 0) {
				printf("0"); return 0;
			}
		}
	}
	printf("%lld", res);
}