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

문제

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

1676번: 팩토리얼 0의 개수

 

처음에 문제를 보고 도통 어떻게 풀어야하는지 답이 안잡혔는데,,

질문 게시판을 잠깐 보고 아이디어를 얻어 바로 풀었다.

 

힌트는 다음과 같다.

뒤에 0이 붙는 개수를 구해야하는데, 0이 붙는다는 것은 10이 한번씩 곱해진다는 것이다.

10의 소인수는 2와 5인데, 보통 2는 5보다 소인수로 많이 가지므로, 곱해지는 5의 개수를 카운트하면 된다.

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string>
#include<cstring>
#include<set>
#include<sstream>
#include<deque>
#include<cmath>
using namespace std;

int n, cnt;

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

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int num = i;
		while (num % 5 == 0) {
			num = num / 5;
			cnt++;
		}
	}

	cout << cnt << "\n";

}