자바 [Algorithm] 이분탐색 - 백준 11687 팩토리얼 0의 개수

1. 문제

 

 

2. 접근법

0이 만들어지는 조건은 2*5가 존재할 때 0이 만들어진다.

2는 2의 배수마다 생성되므로 5의 개수보다 항상 많아 5의 개수에 따라 0의 개수가 정해진다.

5! = 120 - 2^3 * 3 * 5 : 1개

10! = 3628800 = 2^8 * 3^4 * 5^2 * 7 : 2개

소인수분해로 5의 개수를 구하면 된다

 

3. 코드

package week09;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int M = Integer.parseInt(bufferedReader.readLine());

        int left = 1;
        int right = M*5;
        int result = 0;

        while(left <= right){
            int mid = (left+right) / 2;
            int count = 0;
            for (int i = 5; i <= mid; i*=5) {
                count += mid/i;
            }
            if(count > M){
                right = mid - 1;
            }else if(count == M){
                right = mid -1;
                result = 1;
            }else{
                left = mid+1;
            }
        }

        if(result == 0){
            System.out.println(-1);
        }else{
            System.out.println(left);
        }

    }
}

 

4. 후기

소인수분해까진 생각 못해서 다른 블로그들을 참고해서 풀었다..