[프로그래머스 알고리즘 고득점 Kit][이분탐색][Java] 입국심사

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

정답 코드

이분탐색문제라는 것을 알아도... 어떤 것을 기준을 잡을지
참 어려웠다.
그래도 얼마 전에 풀었던 
https://www.acmicpc.net/problem/6236

백준 - 용돈관리와 비슷한 느낌이 들어서
심사하는 데 사용될 전체 시간을 기준으로 하면 될 것을 알았다.
start = 1;

end = 최악의 상황(10억 * 10억) -> 10억 명이 있고 10억 분 걸리는 한 명의 심사관이 있을 때.
나는 기본을 잊어 10억 * 10억이 오버플로우 나버렸다.
int * int 의 결과는 int다. 근데 그 결과 값이 int를 넘어버리기 때문에 오버플로우가 났고
하나를 long으로 바꿔줬다.

그러면 이분 탐색의 세팅이 끝났고
특정 시간이 도달했을 때
가능한 시간인가 아닌가를 어떻게 구해야 할지도 막막했다.
제미나이!! 도와줘!!

아주 작은 힌트를 달랬더니 다줬다.
이런~~
시간이 주어지면 각 심사관이 담당할 수 있는 최대 인원으로 가능 불가능을 계산할 수 있었다.

예를 들어 100명이 있고 3명의 심사관이 (1분, 2분, 4분)이 있다고 가정하자
100분이라는 시간이 가능한지 보려면
각각이 맡을 수 있는 최대인원인 100명 + 50명 + 25명을 계산해 보면 알 수 있다.
현재 심사관만으로 최대 175명을 심사할 수 있다.
그러면 전체 인원인 100명을 넘기니 100분은 여유롭다.
그러면 범위를 줄여서 다시 탐색 - 반복
하면 답이 나온다.

class Solution {
    //심사 받을 사람 n명 (1~1,000,000,000)
    //심사관 m명 (1~100,000)
    //times[i] i번째 심사관의 심사시간 (1~1,000,000,000)
    public long solution(int n, int[] times) {
        long start = 1;
        long end = 1_000_000_000L * 1_000_000_000;
        long ans = 0L;
        while(start <= end) {
            long mid = (start + end)/2;
            if(available(times, mid, n)) {
                end = mid-1;
                ans = mid;
            } else {
                start = mid+1;
            }
        }
        return ans;
    }
    public boolean available(int[] times, long time, int n){
        long availablePeople = 0;
        for(int i=0; i<times.length; i++){
            availablePeople += time/times[i];
            if(availablePeople >= n) return true;
        }
        return false;
    }
}

이분탐색은 부등호 때문에 좀 헷갈리는데
있고 없고를 딱 하나 골라서 그 코드만 이해하려고 노력하면 
좀 더 쉽게 할 수 있을 것 같다.