[백준 3079] 입국심사(Java)

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

이 문제는 이분 탐색을 이용하여 풀 수 있습니다. 이 문제의 가장 어려운 부분은 문제에서 어떻게 이분 탐색을 적용하느냐입니다. 이는 시간을 기준으로 탐색하여 주어진 시간 내에 모든 사람이 탐색이 가능하다면 시간값을 줄이고, 탐색이 불가능하다면 시간값을 늘리는 방식으로 진행합니다. 이 때 시간값이 크기 때문에 이분 탐색으로 탐색 시간을 줄입니다. 시간 체크의 경우 배열의 각 값들로 시간을 나눴을 경우 그 값들의 합이 총 인원 수보다 작다면 가능, 그렇지 않으면 불가능합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        long res = Long.MAX_VALUE;

        long[] arr = new long[N];
        long max = 0;
        for(int i=0;i<N;i++){
            arr[i] = Long.parseLong(br.readLine());
            max = Math.max(max, arr[i]);
        }
        Arrays.sort(arr);

        long start = 0;
        long end = max*M;
        while(start <= end){
            long mid = (start+end)/2;
            long sum = 0;
            for(int i=0;i<N;i++){
                long cnt = mid/arr[i];

                if(sum >= M) break;
                sum += cnt;
            }

            if(sum>=M){
                end = mid-1;
                res = Math.min(res, mid);
            }
            else start = mid+1;
        }

        System.out.println(res);
    }
}