팩토리얼 문제는 수가 기하급수적으로 커지기때문에 항상 자료형, 입력 범위를 잘 봐줘야한다.

이 문제는 팩토리얼 문제인데, 심지어 입력도 <= 10억 조건이 걸려있다.

O(logN)의 알고리즘만 사용이 가능하다.

N!이 약수로 10을 몇개 가지는지 찾으면 N!뒤에 0이 몇개 있는지 찾을 수 있다.
10=2*5 이므로 N!이 약수로 2와 5를 각각 몇개 가지는지 찾아야한다.

10!은 1 2 3 4 5 6 7 8 9 10 으로 이루어져있고, 2를 8개 약수로 가진다.

잘 생각해보면 이는 10/2 + 10/2*2 + 10/2*2*2 이다.

마찬가지로 약수로 5를 몇개 가지는지 찾아주면되고,

둘 중 최솟값을 출력해주면된다

1. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t,n;
    cin >> t;
    while(t--) {
        cin >> n;
        int cnt_2=0;
        int cnt_5=0;
        for(int i=2;n>=i;i*=2) {
            cnt_2+=n/i;
        }
        for(int i=5;n>=i;i*=5) {
            cnt_5+=n/i;
        }        
        cout << min(cnt_2, cnt_5) << '\n';
    }
    
    
    return 0;
}

2. 느낀 점

(1) 아이디어 떠올리기

이 문제의 아이디어는 사실 시간복잡도를 기반으로 떠올리는 방법 밖에 없을 것 같다.
사용 가능한 알고리즘의 시간복잡도가 O(logN)이다.

O(logN)이면 어떤 수가 계속 곱해지며, 그 값이 N보다 작은 동안 반복을 수행하는 것이다.

예를들어 아래와 같다.

for(int i=2;n>=i;i*=2) {
            cnt_2+=n/i;
        }

시간복잡도를 기반으로 알고리즘을 떠올리는 것도 생각해보자.

n!이 k를 몇개 약수로 가지는지 확인하는 방법을 가능하면 외워두는 것도 좋을 것 같다.