[백준] 1676_팩토리얼 0의 개수

실제 팩토리얼 값을 구할 필요없다. 팩토리얼의 정의를 보면

\[n! = n\times(n-1)\times(n-2)\times\cdots\times 2\times1\]

(예)

\[10! = 10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1\]

문제는 일의 자릿수부터 시작해서 처음으로 0이 안나오는 자릿수까지의 0의 개수를 구하는 것이고, 위 식에서 두 수를 곱해서 10이 나오려면 \(10\times 1\)또는 \(5\times 2\)이다. 그러면 결국 나머지 숫자들의 곱에(마지막 자리가 결코 0이 되지 않는다) 100을 곱한 꼴이 되어 0의 개수는 2개다. 이런 식으로 생각하다 보면 0이 추가되는 규칙이 발견되는데,

• 125의 배수일 때는 0이 3개 추가 -> \(125= 5^3\)
• 25의 배수(125의 배수는 아닌)일 때 0이 2개 추가-> \(25 = 5^2\)
• 5의 배수(25의 배수, 125의 배수는 아닌)일 때 0이 1개 추가 -> \(25 = 5^1\)

이러한 규칙을 가지고 0을 세어주면 답이다. 아래는 이것을 구현한 코드다.

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N;
	cin >> N;
	int cm5 = 0;
	for (int i = 1; i <= N; ++i) {
		if (i % 125 == 0) cm5 += 3;
		else if (i % 25 == 0) cm5 += 2;
		else if (i % 5 == 0) cm5 += 1;
	}
	cout << cm5 << '\n';
	return 0;
}