교수가 된 현우

이 강의에서 설명은 했지만 이문제 분할 정복으로 팩토리얼 계산해서 풀려니까 도저히 답이 안나왔었음.

근데 이문제는 팩토리얼 다 계산 안하고

2400 같은 수 가 있을 때 뒤에 00을 구하는 문제이다. (팩토리얼 계산을 다 안하고).

펙토리얼 0 개수

위의 문제는 교수가 된 현우의 하위버젼 문제인거같다.

2500 은 25 * 100이다.

100은 10 * 10이다.

10은 2 * 5이다.

여기서 아! 싶더라...

10은 2와 5를 통해서 구할 수 있고

2와 5가 1개씩 있으면은 10을 하나 만들 수 있다.

2와 5가 두개씩 있으면 100을 만들 수 있다.

이런식으로 나열을 해서 2가 몇개 있는지 구할 수 있다.

그리고 5의 개수도 몇개 있는지 구한다음에 둘의 최소 공배수를 구해준다.

그러면 2개가 나옴. 이개 오른쪽 끝에 있는 0의 개수이다.

실제로 10! 계산해보면은

정리하자면

2의 제곱승 수로 2^n으로 10!의 값중에 2가 몇개 들어있는지 알 수 있다는 말이다.

처음에 이런식으로 2의 갯수를 구하는데

두번째 줄은 10 / 4 => 2가 나옴

3번째줄음 10 / 8 => 1이 나옴

그래서 2의 제곱수로 10!의 값에 2가 몇개 있는지 알 수 있다는 말이다.

5도 마찬가지로 5의 제곱승수로 나누면서 몇개있는지 구한다음에

2의 갯수와 5의 갯수의 최대공배수를 구하면된다.

아래 코드를 보면은

for (int j = 2; j <= N; j *= 2)
{
	ret1 += N / j;
}

이부분이 지금 10을 2로 나누었을 때 몫을 ret1에 더하고

그다음에 10을 4로 나누었을때 몫을 ret1에다 축적해서 더하는 부분이다.

ret2도 이런식으로 다 구한다음에 ret1, ret2중에서 최소값을 찾으면 된다.

최소값을 찾는 이유는 생각해보도록 !

cpp 코드

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 101
#define ll long long

int T, N;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;
	
	for (int i = 0; i < T; ++i)
	{
		cin >> N;
		int ret1 = 0, ret2 = 0;
		for (int j = 2; j <= N; j *= 2)
		{
			ret1 += N / j;
		}
		for (int k = 5; k <= N; k *= 5)
		{
			ret2 += N / k;
		}
		cout << min(ret1, ret2) << endl;
	}
	
	return 0;
}