백준 1676 - 팩토리얼 0의 개수

문제 설명

문제풀이 : 예를 들어 111533400 이라는 숫자가 있다고 하면 뒤에서부터 0이 아닌 숫자가 나올때까지 0의 숫자를 세는 문제이다. 이 경우에 0의 개수는 2개이다.

 

첫번째 풀이 : 실제로 n!을 계산하여 하려고 하였지만, 범위를 한참 벗어나서 구하지 못하였다.

두번째 풀이 : 소인수 분해를 하여 2*5의 갯수에 따라 0의 갯수가 정해지는 것을 깨달았다. 
그래서 곱해지는 숫자마다마다를 소인수 분해하여 2의 갯수와 5의 갯수를 각각 구했다. 

 

10 = 2*5 => 2(1개) 5(1개)

 

위와 같은 방식으로 팩토리얼 계산시 곱해지는 수들의  소인수중 2와 5의 개수를 구하였다. 
2와 5가 하나씩 짝을 이루어야 0이 되므로 2의 개수와 5의 개수중 최소값을 구하면 되는 문제이다. 

 

*알고리즘은 쉽게 짰으나, 코딩에서 시간이 걸렸다. 

 

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int two_detec(int n)
{
	int cnt = 0;
	while (n%2==0)
	{
		cnt++;
		n = n / 2;
	}
	return cnt;
}


int five_detec(int n)
{
	int cnt = 0;
	while (n%5==0)
	{
		cnt++;
		n = n / 5;
	}
	return cnt;
}

int main()
{
	int N;
	int Limit;
	int cnt = 0;//0의 갯수
	cin >> N;
	Limit = N;
	int two = 0;
	int five = 0;
	for (int i = Limit; i > 1; i--)
	{
		two += two_detec(i);
		five += five_detec(i);
	}
		cnt = min(two, five);
	cout << cnt;
	return 0;
}