[백준] 알고리즘 1676번 - 팩토리얼 0의 개수

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,cnt=0;
	cin >> n;

	for (int i = 2; i <= n; i++) {
		if (i % 5==0) cnt++;
		if (i % 25==0)cnt++;
		if (i % 125==0)cnt++;
	}
	cout << cnt;
}
 

N의 범위가 500까지이므로 어느세월에 500!구해서 0의개수를 뽑아내는건 범위도 초과할뿐더러 문제의 의도와는 맞지않다.

그렇다면 어떻게 해결해야할까

2x5 = 10 이라는걸 눈치챗다면 (2,5)의 쌍을 몇개로 만들 수 있는지 확인하면 된다.

즉, 팩토리얼의 결과의 인수들의 2,5의 쌍의 갯수가 0의 최종 개수가 될 것이다.

2는 짝수의 배수이므로 5의 개수보다 무조건 많이 때문에, 5의 개수만 카운트해서 정답을 도출 할 수 있다.

5일경우 2x5의 쌍을 한개 만들 수 있으므로 카운트해준다.

25일 경우 2x5x2x5의 쌍을 두개 만들 수 있으므로 5에서 한번 해주고 25에서 한번 해줘서 총 2개의 카운트를 도출한다.

125도 마찬가지이다.