[백준 11687번] 팩토리얼 0의 개수 (C++)

문제링크 : https://www.acmicpc.net/problem/11687

11687번: 팩토리얼 0의 개수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int M;

int func(int n) //n!에서 5의 갯수 카운팅
{
    int cnt = 0;
    while(n>=5)
    {
        n/=5;
        cnt+=n;
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> M;

    int l = 1, r = 1000000000, result;

    while(l<=r)
    {
        int mid = (l+r)/2; //N!
        int cnt = func(mid); //N!의 5의 갯수

        if(cnt<M) l = mid + 1; //N! 증가
        else 
        {
            result = mid;
            r = mid-1; //N! 감소
        }
    }

    cout << ((M==func(result) ? result : -1));

    return 0;
}

 

우선 0의 개수를 알기 위해선 10의 개수를 알아야한다.

10은 2*5이므로 2또는 5의 개수를 파악하는 것으로 알 수 있다.

2의 개수는 짝수 일 때마다 계속해서 생기지만, 5의 개수는 5의 배수 일때만 생기므로 5의 개수만 카운팅 해주면 된다.

 

M의 범위가 10억까지이므로, 이분탐색을 이용해 풀어준다.

N!을 mid 값으로 잡고, 해당 mid 값의 5의 개수가 몇 개나 되는지 카운팅 후 반환해준다.

 

만약 해당 카운팅이 M보다 작다면 mid 값을 1 증가시켜 N!의 값이 더 커지도록 해주고,

카운팅이 M보다 크거나 같다면 해당 mid 값 저장후, 더 나은 값 탐색을 위해 mid 값을 1 감소시켜 N!의 값이 더 작아지도록 해준다.

 

이후 저장했던 mid 값의 5의 개수가 M과 같다면 해당 mid 값을, 아니라면 불가능한 케이스이므로 -1을 출력해준다.