프로그래머스 입국 심사

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times); 
        
        long st =1;
        long en =(long) n*times[times.length-1];
        
        long answer = en;
        
        while(st<=en){
            long mid = (st+en)/2;
            
            long people = 0;
            
            for(int i=0; i<times.length; i++){
                people += mid/times[i];
            }
            
            if(people<n){
                st = mid+1;
            }else{
                answer = mid;
                en = mid-1;
            }
            
        }
        
        
        return answer;
    }
}

이분탐색을 사용하는 것 자체는 그리 어렵지 않으나!!!! 아이디어를 짜내는데 조금(많이)힘들었습니다!

우선 범위가 10^9으로 n^2은 꿈도 못꾸는 상태이며 logN으로 떨궈야할 때 그럴 때 이분탐색을 사용합니다!!!

우선 로직이 왜이렇게 나오는지 체크 먼저 해보자 ㅠㅠ

문제에서 주어진 예시를 가지고 생각해보자
n=6이고 가장 길게 심사하는 사람이 10분인 경우
시간이 가장 오래 걸리는 케이스는 6 * 10이 된다.

해당 시간의 범위가 우리가 찾으려는 최단 시간의 범위가 된다.

그럼 st를 1로 주고
en를 n명 * 입국 심사하는데 가장 오래 걸리는 사람
으로 값을 지정하면 된다.

  for(int i=0; i<times.length; i++){
                people += mid/times[i];
            }
            

여기서 mid값은 (st+en)/2의 값이 된다.
즉 여기서는 초기 값이 61/2 = 30이 되는 것

mid 값에 times의 값을 나누고 해당 값을 people에 저장한다.
해당 값은 주어진 시간 mid 안에 총 몇 명의 사람을 검사 할 수 있는지 의미하고 있다.

즉 30초의 경우 7X4<30 이니 4명의 사람을 검사할 수 있고
10X3 <=30 이니까 3명의 사람을 검사할 수 있다.
즉, 7초 짜리 검사관이 4명 10초짜리 검사관이 3명 검사가 가능해서 총 7명 검사가 가능하단 뜻이다.

			 if(people<n){
                st = mid+1;
            }else{
                answer = mid;
                en = mid-1;
            }

이제 우리가 지정한 사람이 n보다 작다고 가정하자
그렇다면 범위를 더 큰쪽으로 키워야한다. end를 줄어들게하면 mid가 줄어드니까
st = mid+1을 통해 더 큰 범위에서 찾도록 하자

만약에 people>n보다 큰 경우는
범위를 줄여야하는 경우니가 en = mid-1을 통해 값을 줄이도록 하자

그렇다면 1+60 이었던 값이 1+(30-1)이 된다. 위와 같은 과정을 계속 거쳐서!...

en이 st보다 작아지는 순간! while문을 빠져나오게 된다. 이때 else문을 거쳐서 answer 는 우리가 원하는 값 28이 나오게 된다.

REVIEW:

아이디어를 짜내는 게 어려웠어요 ㅠㅠㅠ 아직 많은 유형을 담아보지 못해서 그런것 같아욤