[백준 15810] 풍선 공장(Java)

문제

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

풀이

이분탐색을 이용해서 최소 시간을 찾는다.

left값과 right 값이 있고 중간 값을 mid라고 할 때,
시간이 mid 값일 때 풍선을 몇 개 만들 수 있는지를 구한다.

만들 수 있는 풍선의 개수가 M보다 작을 경우 mid 값의 오른쪽 값들을 서치
M보다 크거나 같을 경우 mid 값의 왼쪽 값들을 서치한다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int[] timeOfStaff = new int[N];
        for(int i=0;i<N;i++){
            timeOfStaff[i] = scan.nextInt();
        }
        Arrays.sort(timeOfStaff);

        long left = 0L;
        long right = (long)timeOfStaff[0]*(long)M;

        while(left<=right){
            long mid = (left+right)/2;
            long rem = 0;
            for(int i=0;i<N;i++){
                rem += mid/(long)timeOfStaff[i];
            }
            if(rem<M){
                left = mid+1;
            }
            else{
                right = mid-1;
            }
        }
        System.out.println(left);
    }
}```