[백준 / BOJ] C++ 1676 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

문제

 

풀이

팩토리얼 계산을 하게되면 적은숫자면 모르지만 큰수를 입력할 경우 오버플로우 오류가 생긴다. (숫자가 너무 커서)

문제를 풀어서 생각해보면, 0이 아닌 숫자가 나올 때 까지 0의 개수를 구하는것이다.

처음 0이 아닌 숫자가 나오는 경우는 10의 거듭제곱 밖에 없다. 결국 10은 2와 5로 소인수 분해를 할 수가 있다.

 

숫자는 2부터 입력받은 수까지 반복하며 소인수 분해한 2와 5중 더 작은 개수를 출력하면 된다.

 

Code ( C++ )

#include <iostream>
using namespace std;

int num2 = 0;
int num5 = 0;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;

	cin >> n;

	int temp;

	//2와 5의 개수
	for (int i = 2; i <= n; i++)
	{
		temp = i;
		// 2
		while (temp % 2 == 0)
		{
			num2++;
			temp /= 2;
		}
		// 5
		while (temp % 5 == 0)
		{
			num5++;
			temp /= 5;
		}
	}
	cout << min(num2, num5);
}