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

 

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

11687번: 팩토리얼 0의 개수

 

#문제 간단 정리

이하생략

 

#문제 해결 방법

끝의 0의 개수는 2*5의 개수로 정해지고,

2는 2의배수만큼 5는 5의 배수만큼 존재하기 때문에 2가 항상 5보다 많다

때문에 5의 개수만 세주면 0의 개수와 같다

 

이분탐색의 범위는 m*5! 이 무조건 m개의 5의개수보다 많은 5를 가지므로

right를 m*5로 설정해주면 된다.

 

또한 포함된 5의 개수는 5부터 5의제곱수들을 차례대로 나눈 몫을 구하면 5의 개수를 구하는

함수를 만들 수 있다.

 

#전체 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;


//5가 들어간 개수를 찾는 함수
int findFive(int a) {
    int count = 0;

    for (int i = 5; i <= a; i *= 5) {
        count += (a / i);
    }
    return count;
}

int main() {

    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    //0의 개수는 5의 개수와 동일
    //제곱이 나오는 경우는 숫자가 건너뛰어짐
    int input;
    cin >> input;

    int left = 1;
    int right = input*5;
    int target = input;
    int result = 0;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (findFive(mid) == target) {
            right = mid -1;
        }
        else if (findFive(mid) > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    
    if (findFive(left) == target) {
        cout << left;
    }
    else {
        cout << -1;
    }
    
    return 0;
}