백준 15810번 풍선 공장

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

15810번: 풍선 공장

 

저는 해당 문제를 이분탐색으로 해결하였습니다.
저는 이분 탐색을 통해 해당 시간동안 m 개의 풍선 이상을 만들수 있는지를 확인하고, m개 이상으로 만들 수 있다면 end를 mid-1로 줄여 낮은 값을 탐색하게 하고, m 개 이하라면 start를 mid+1로 올려 높은 값을 탐색하도록 구현하였습니다.

 

package BOJ.binarysearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_15810 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[] input = new int[n];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < n ; i++){
            input[i] = stoi.apply(st.nextToken());
        }
        long result = binearySearch(input,n,m);
        System.out.println(result);
    }
    private static final long MIN = 0;
    private static final long MAX = 1_000_000L *  1_000_000L;
    private static long binearySearch(int[] input, int n, int m) {
        long start = MIN;
        long end = MAX;
        long result = MAX;
        while(start <= end){
            long mid = (start + end)/2;
//            System.out.println(mid);
            if(check(input,n,mid,m)){
                result = mid;
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return result;
    }

    private static boolean check(int[] input, int n, long time, int m) {
        long cnt = 0;
        for(int i = 0 ; i < n ; i++){
            cnt += time / input[i];
        }
        if(cnt >= m){
            return true;
        }
        return false;
    }
}