BOJ : 11687

1. 문제

 

2. 문제 설명 및 알고리즘 설계

 

끝이 0이 되려면 2와 5가 필수로 필요하므로 5의 개수를 를 체크 하면서 해준다.

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

 

3. 코드

package week9;

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

public class Q11687_boj {
    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;
    }
}

 

4. 시간 복잡도

O(logN)

 

5. 결과

 

문제가 이해가 잘 안되가지고 다른 사람들의 풀이를 많이 참고해버렸습니다.. 다음에는 절대 안틀립니다..