팩토리얼 0의 갯수 찾기, 콤비네이션 0의 갯수 찾기(Baekjoon 1676, 2004)

팩토리얼 0의 갯수

아마 주어진 n에 대해 n!의 0의 갯수를 구하라는 문제가 주어진다면

약수로 2와 5를 가지는 수들을 활용해야할 것 같기는 한데 구체적으로 어떻게 해야할지 몰라서

헤매는 경우가 대부분일 것이다.

하지만 거기서 생각을 조금만 발전시켜본다면 충분히 문제를 잘풀 수 있다.

일단 n!에대해 0의 갯수는 2 x 5의 조합에 의해서 생성된다.

그런데 2의 배수들은 모두 2를 약수로 가지고있기 때문에 n!은 충분히 많은 2를 가지고있고 

결국은 5의 갯수에 의해 0의 갯수가 좌우된다고 생각할 수 있다.

예를들어 50!에서 0의 갯수를 구한다고 생각해보자.

5를 약수로 가진 숫자는 5 , 10 , 15 , 20 .... 50 이고 5의 갯수는 50/5 = 10이 된다.

하지만 여기서 우리가 간과한 점은 25는 5*5라는 점이다 

즉 5^n의 배수들은 5를 다른 5의 배수보다 더 갖게된다.

ex) 25의 배수인 25,50은 5를 2개씩 가짐

고로 50같은 경우 5의 갯수는 50/5 + 50/25 = 12개가 되며

0의 갯수도 12개라고 생각할 수 있다.

문제를 통해서 적용해보자.

#include <iostream>

using namespace std;

int main()
{
	int N;
	scanf("%d", &N);

	int result = 0;
	if (N < 25) result += N / 5;
	else if (N < 125) result += N / 5 + N / 25;
	else result += N / 5 + N / 25 + N / 125;

	printf("%d\n", result);
}

조합 0의 갯수

조합을 수식으로 나타내면 다음과 같다.

펙토리얼로 표현되어 있기 때문에 위에 있는 펙토리얼을 통해 0의 갯수를 구하는 방법을

조금만 응용하면 조합의 0의 갯수도 구할 수 있다는 것을 느낄 수 있을것이다.

다만 조합의 경우에는 나눗셈이 있기때문에 약수가 2인것의 갯수를 쉽게 판단할 수 없으며

결국 2의 갯수와 5의 갯수를 모두 count해주어야 0의 갯수를 알 수 있다.

문제를 통해 코드를 작성해보자.

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

long long count5(long long num);
long long count2(long long num);
int main()
{
	long long n, m;
	scanf("%lld %lld", &n, &m);
	long long result1 = count5(n) - count5(m) - count5(n - m);
	long long result2 = count2(n) - count2(m) - count2(n - m);
	printf("%lld\n", min(result1, result2));
}
long long count5(long long num)
{
	long long result = 0;
	long long x = 1;
	for (long long i = 1; ;i++) {
		x *= 5;
		if (num >= x) result += num / x;
		else break;
	}
	return result;
}
long long count2(long long num) {
	long long result = 0;
	long long x = 1;
	for (long long i = 1; ;i++) {
		x *= 2;
		if (num >= x) result += num / x;
		else break;
	}
	return result;
}

5의 갯수를 구하는 함수, 2의 갯수를 구하는 함수를 따로 작성하여 적용하였다.

따로 함수를 작성하지 않고 main함수 안에서 모든 과정을 한번에 수행하도록 하는

반복문을 작성한다면 보다 간결하게 코드를 짤 수도 있다.