[C++]백준1676번 팩토리얼 0의 개수

오늘은 백준1676번 팩토리얼 0의 개수 문제를 풀어보도록 하자.

무작정 다 곱해서 0의 갯수를 구하는건 무조건 TLE일 뿐만 아니라 long long 타입을 써도 overflow가 날 것이 뻔하다.

따라서 소인수분해를 이용하여 푼다.

문제는 다음과 같다.

                               [접근법]

  1. 뒤에 0이 붙을 수 있는 조건은 10을 곱해주면 된다. 2가 1개, 5가 1개면 된다.
  
  2. 하지만 더 깊게 생각해보면 2의 갯수는 5의 갯수보다 무조건 많을 것이다. 왜냐하면 짝수는 그 값의 절반 이상만큼 있고,
     5의 갯수는 5의 배수에서만 뽑아낼 수 있기 때문이다.

  3. 따라서 2의 배수를 따지지 말고 5의 배수를 뽑아내서 5가 몇개있는지 카운팅만 해주면 된다. 코드는 매우 간단하다.

                                     [코드]
#include <iostream>
using namespace std;

int cnt_5 = 0;

int main() {
	int N;

	cin >> N;

	for (int i = 1; i <= N; i++) {
		int tmp = i;
		if (i % 5 == 0) {
			while (tmp % 5 == 0) {
				tmp /= 5;
				cnt_5++;
			}
		}
	}
	cout << cnt_5 ;
	return 0;
}