[Baekjoon/JAVA] 3079 입국심사

 

 

이분 탐색을 잘 못하는 거 같아서 연습하려고 푼 문제

근데 어떻게 이걸 이분탐색으로 풀 수 있는지 잘 감이 안와서 애먹었다.

 

 

모든 사람이 심사를 받는 데 걸리는 시간을 이분 탐색으로 찾으면 되는 문제였음 !!

해당 시간을 mid값으로 갱신하면서 찾으면 되는데, 

 

해당 mid 시간동안 모든 심사대에서 각각 몇명 심사할 수 있는지를 더해주면서 

조건을 충족하지 못 한다면 시간을 늘려주고 (left 값 갱신)

조건을 충족한다면 시간을 줄여준다. (right 값 갱신)

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int[] arr = new int[N];
        long left = Long.MAX_VALUE;
        long right = 0;

        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            left = Math.min(left, arr[i]);
            right = Math.max(right, arr[i]);
        }

        Arrays.sort(arr);
        // 최대값: 가장 오래걸리는 심사관한테 M명이 전부 심사받음
        right *= M; 

        long res = 0;
        while (left <= right) {
            // mid값: 가능한 모든 시간대 중 최적의 시간 탐색
            long mid = (left + right) / 2;
            long cnt = 0;
            for (int i=0; i<N; i++) {
                // mid 시간동안 i 번 심사대에서 몇명 받을 수 있는지 더해줌
                cnt += (mid / arr[i]);
                // 가능하다면 더이상 확인하지 않음
                if (cnt > M) {
                    break;
                }
            }
            // 가능하지 않다면 숫자 키우기
            if (cnt < M) {
                left = mid + 1;
            }
            else {
                // 가능하다면 숫자 줄이기
                right = mid - 1;
                res = mid;
            }
        }
        System.out.println(res);
    }
}