[lv.3] 입국심사

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

• 문제
  

• 풀이
  1) 이분탐색에서 구할 mid를 n명을 전부 상담할 수 있는 최소의 시간으로 한다. 이때 left는 1, right는 times 중에서 가장 시간이 오래 걸리는 놈*n으로 한다.
  2) mid/times[i]는 i번째 심사대에서 주어진 시간동안 상담할 수 있는 사람들의 수. 0~length-1까지 전부 더한다.
  3) 위의 수가 n 이상일 경우, mid안에 전부 가능하다는 뜻이므로 right를 내린다.
  4) 미만일 경우, mid 안에 불가능하다는 뜻이므로 left를 올린다.

• 소감
  사실 mid를 어떻게 설정할까는 바로 생각해냈는데 문제는 시간계산, 사실 진짜로 시뮬레이션을 돌려서 했더니 바로 시간초과가 떴기에 50분동안 고생해서 도저히 몰라 답안을 봤는데 저지랄인거 보고 내가 말하는 감자새끼인 것을 깨달았다.

• 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long left = 1;
        long right = (long) times[times.length-1]*n;
        long answer = right;
        while(left<=right){
            long mid = (left+right)/2;
            long now = 0;
            for(int i=0; i<times.length; i++){
                now += mid/times[i]; // 심사 한 줄에서 받을 수 있는 사람 수
                if(now >= n) break;
            }
            if(now>=n){
                right = mid-1;
                answer = Math.min(answer, mid);
            }
            else left = mid+1;
        }
        return answer;
    }
}