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

11687번 : 팩토리얼 0의 개수

---

 

문제)

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 찾는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.

 

 

 

출력 :

가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 출력한다. 그러한 N이 없는 경우에는 -1을 출력한다.

 

 

 

 

 

 

풀이)

뒷 자리에 0이 만들어지는 이유는 2 * 5 가 존재하기 때문이다.

 

팩토리얼이 진행되면서 (1 * 2 * 3 * 4 .....) 2의 배수는 무조건 많기 때문에 5의 배수를 이진 탐색을 통해 세어주면 된다.

 

// 11687. 팩토리얼 0의 개수
#include <iostream>
#include <climits>
 
using namespace std;
 
int n;
 
int check(int x)
{
    int cnt = 0;
    for (int i = 5; i < x + 1; i *= 5)
    {
        cnt += (x / i);
    }
 
    return cnt;
}
 
int main()
{
    cin >> n;
 
    long long s = 1;
    long long e = INT_MAX;
 
    int ans = 0;
    while (s <= e)
    {
        int mid = (s + e) / 2;
        
        int c = check(mid);
        if (c >= n)
        {
            if (c == n) ans = mid;
            e = mid - 1;
        }
        else
        {
            s = mid + 1;
        }
    }
 
    if (ans == 0) cout << -1;
    else cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/11687 

11687번: 팩토리얼 0의 개수