백준 2004 - 조합 0의 개수(상세풀이)

문제는 링크로 대체합니다.

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

2004번: 조합 0의 개수

n과 m이 주어졌을 때 조합 nCm값의 끝에 0이 몇자리가 있는지 구하는 문제입니다. 직관적으로 봤을 때 n!과 m! n-m! 세가지를 직접구한후 0의 개수를 구하면 될 것 같지만 n,m의 범위가 20억이기 때문에 20억! 의 값은 상상도 할 수 없을만큼 큰 수이기 때문에 long long 자료형을 쓴다고 하더라도 저장할 수 없습니다. 때문에 20억!의 값을 구하지 않고도 0의 개수를 구할 수 있어야합니다. 

 

그렇다면 0의 개수는 어떻게 구할 수 있을까요? 끝자리에 0이 5개있는 수는 또 다른 수식으로 n * 10^5 로 표현할 수 있습니다. 이 수를 소인수 분해하면 5와 2의 짝이 5개 있다는것입니다.

 

nCm의 값은 n!/m!*(n-m)! 이므로 각 n!, m! (n-m)!의 2와 5의 개수를 구한뒤에 n!의 2의개수에 m!과 (n-m)!의 2의 개수를 합한값을 빼줍니다. 2의 개수를 빼주는것은 수식에서 약분을 하는것과 동일한 의미를 나타내기 때문입니다. 마찬가지로 5의 개수도 같은 식으로 구하여 nCm의 2의개수와 5의개수를 구한뒤 min(2, 5)를 사용하면 2와5의 짝을 구할 수 있습니다.

 

그렇다면 임의의 수 k팩토리얼을 소인수 분해 하였을 때 i의 값이 몇개 있는지 알아내는 알고리즘을 구현해야합니다. 여기서도 단순히 k부터 시작하여 i로 나누어지는 횟수를 구하면 될 것 같지만 이렇게 할 경우 n의 최대값이 20억이기 때문에 for문을 20억번 수행해야합니다. 이렇게 할 경우 당연히 시간초과가 발생하겠죠.

 

그래서 더욱 빠른 방법이 필요합니다. 예를들어 9!의 값을 소인수 분해 하였을 때 3의 개수를 구한다 보겠습니다.

9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 입니다. 여기서 3의 배수는 보두 3을 1개이상 보유하고 있습니다. 그리고 3의 제곱인 9는 3의배수에서 3을 하나 셈을 하더라도 3이 하나 더 남아있습니다. 그래서 여기서 3의 개수는 3, 6, 9에 하나씩 있고 9에는 3을 하나 빼고도 하나더 있으므로 총 4개가 있습니다. 즉 k!의 i개수를 알려면 ∑k/i^n 값을 구하면 됩니다. 

 

이 알고리즘을 통하여 2와 5의 개수를 구하고 끝자리 0의 개수를 출력할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <queue>

using namespace std;

#define MAX 100000

long long int n, m;
pair<long long, long long> calc_zero(long long n_factorial) {
	long long two = 0;
	long long five = 0;
	for (long long i = 2; i <= n_factorial; i *= 2) {
		two += n_factorial / i;//2의개수
	}
	for (long long i = 5; i <= n_factorial; i *= 5) {

		five += n_factorial / i;//5의개수
	}

	return { two, five };
}

int main()
{
	scanf("%lld %lld", &n, &m);
	pair<long long, long long> n_zero = calc_zero(n);
	pair<long long, long long> m_zero = calc_zero(m);
	pair<long long, long long> nm_zero = calc_zero(n - m);
	printf("%d", min(n_zero.first - (m_zero.first + nm_zero.first), n_zero.second - (m_zero.second + nm_zero.second)));
}