(C++) 백준 1676번 - 팩토리얼 0의 개수

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

문제

> N!에서 뒤에서부터 처음 0이 아닌 수가 나올때 까지의 0의 개수를 구해라.

접근

0을 발생시키는건 2x5일 때이므로 N을 소인수 분해 했을때 2x5의 개수를 보면 되는데 2와 5중 더 작은 개수를 세면 된다.
하지만 2는 모든 짝수에 들어 있으므로 5가 항상 적기 때문에 5의 개수를 세면 된다.
N에서 5의 배수의 개수는 N/5하면 되므로 해당값을 cnt에 누적하고, 5의 제곱, 세제곱은 각각 5가 더 들어있으므로 추가로 더 누적해준다.

문제해결

> 5의 배수의 개수만 찾으면 되므로 입력으로 들어온 수 보다 작거나 같을 때까지 반복하며 5의 배수의 개수를 누적한다. 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;
	int cnt = 0;

	for (int i = 5; i <= N; i *= 5)
	{
		cnt += N / i;
	}
	cout << cnt;
}

후기

팩토리얼에서 뒤에 0의 개수의 로직이 2x5의 개수 중 더 적은수 즉, 5의 개수를 찾으면 되는걸 새로 알게 됐다. 흥미롭다.