[백준] 3474번 교수가 된 현우

#include "bits/stdc++.h"

using namespace std;


void Check(int num)
{
	int cnt2 = 0;
	int cnt5 = 0;

	int temp = 2;

	while (num >= temp)
	{
		temp *= 2;
	}

	temp /= 2;

	while (temp >= 2)
	{
		cnt2 += (num / temp);

		temp /= 2;
	}



	int temp2 = 5;

	while (num >= temp2)
	{
		temp2 *= 5;
	}

	temp2 /= 5;

	while (temp2 >= 5)
	{
		cnt5 += (num / temp2);

		temp2 /= 5;
	}

	cout << min(cnt2,cnt5) << '\n';
}


int main() {

	int n;
	vector<int> v;
	cin >> n;

	for (int a = 0; a < n; a++)
	{
		int n;

		cin >> n;
		v.push_back(n);
	}

	

	for (int num : v)
	{
		Check(num);
	}
}

 

사실 이문제는 아이디어가 정말 중요한 문제였다.

 

일단 범위가 10억이기 때문에 10억 팩토리얼을 실제로 구한다는 것은 절대로 불가능한 일이다.

 

그러나 우리가 알아야 하는것은 0의 갯수이기 때문에 이부분에 착안해서 아이디어를 내야 한다.

 

0의 갯수라는 것은 바로 10이 몇번이나 곱해졌나이다.

 

10은 2와 5의 곱으로 이루어져있다.

 

그렇다면 10으로 예를 들어보도록 하겠다.

 

10! = 10x9x8x7x6x5x4x3x2x1이다.

 

여기엔

 

2는 4번

 

4는 2번

 

8은 1번

 

즉 2는 총 7번 곱해졌다.

 

5는 1번

 

10은 1번

 

5는 총 2번 곱해졌다.

 

그러므로 10은 10!팩토리얼에 2번 곱해져있다는 것을 알 수 있고

 

10!의 0의 수는 2개라는 것을 알 수 있다.

 

이러한 아이디어를 기반으로 문제를 풀었다.