백준 11687[자바] java 팩토리얼 0의 개수

 

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

11687번: 팩토리얼 0의 개수

 

▶문제

 

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

 

▶입력

 

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

 

▶출력

 

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

 

▶해설

 

M의 크기가 1억이므로 이분 탐색을 활용해서 탐색해야 합니다. 이때 0이 만들어지는 조건을 생각하면 됩니다.

 

0이 만들어지는 조건은 2*5가 존재할 때입니다. 이때 2는 2의 배수마다 생성되므로 5의 개수보다 항상 많습니다.

따라서 5의 개수에 따라 0의 개수가 결정됩니다. 그렇다면 55일 때 5의 개수가 몇 개인지 파악하는 방법은 쉽습니다. 

5의 거듭제곱들로 나누었을 때 의 몫들입니다. 따라서 아래와 같은 식을 구할 수 있습니다. 

 

private static int solve(int mid){
    int count=0;

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

    return count;
}

 

이제 이분탐색의 범위를 지정합니다. left는 1이고, right는 m*5로 진행해줍니다. m과 5의 개수가 연관성이 있기 때문입니다. 이때 주의할 점은 m과 정확하게 같은 개수가 존재하는지 체크하고 없을 경우 -1을 출력하기 위해 check 불린 값을 사용해야 합니다. 

 

while(left<=right){
    int mid = (left+right)/2;
    if(solve(mid)>m){
        right=mid-1;
    } else if(solve(mid)==m){
        right=mid-1;
        check=true;
    }
    else{
        left = mid+1;
    }
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;
import java.util.Arrays;


public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int m = Integer.parseInt(br.readLine());

        int left=1;
        int right=m*5;

        boolean check=false;
        while(left<=right){
            int mid = (left+right)/2;
            if(solve(mid)>m){
                right=mid-1;
            } else if(solve(mid)==m){
                right=mid-1;
                check=true;
            }
            else{
                left = mid+1;
            }
        }

        if(check){
            System.out.println(left);
        }else{
            System.out.println(-1);
        }
    }

    private static int solve(int mid){
        int count=0;

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

        return count;
    }
}