1676번

1676번 - 팩토리얼 0의 개수

언뜻 보면 N의 범위가 400!...

이 엄청난 수를 어디에 담아야할지 조차 보자마자 머리가 아득해졌다. 근데 항상 이럴수록 더 힌트가 되는 것 같다.

오히려 너무 크기 때문에 다른 방법을 생각해보게 되었다.

호랑이 굴에 들어가도 정신만 바짝!

소인수 분해를 통해서 2와 5의 갯수를 구하고, 2와 5의 갯수의 최솟값을 출력하면 된다.

최종적으로 10의 갯수만 구하면 되기 때문이다.

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
int main()
{
    int N;
    int cnt2 = 0;
    int cnt5 = 0;
 
    cin >> N;
 
 
    for (int i = N; i >= 1; i--)
    {
        int x = i;
        while (x % 2 == 0)
        {
            cnt2++;
            x /= 2;
        }
 
        while (x % 5 == 0)
        {
            cnt5++;
            x /= 5;
        }
    }
 
    cout << min(cnt2, cnt5) << endl;
 
 
    return 0;
}