모든 사람이 심사를 받는데 걸리는 시간을 최소로 하는 값을 구해보자.

→ 문제의 제약 조건의 n과 심사대의 개수의 최대값이 매우 크다.

시간 초과가 나기 쉬운 문제로 제약 조건을 고려해야 한다.

따라서 완전탐색으로는 불가능하다고 판단하여 DP나 이분탐색을 사용하여 가능한 모든 시간 중에서 대기 인원을 모두 처리할 수 있는 경우를 찾는 풀이를 선택했다.

1. 가장 느리게 처리하는 심사대와 빠르게 처리하는 심사대를 찾기 위해 정렬한다.

2. 최악의 경우는 가장 오래는 걸리는 심사대가 모든 사람을 처리하는 경우 → time * n

3. mid의 시간 동안 몇 명의 사람을 처리할 수 있는지 확인한다.

   → mid / time = 탐색대마다 시간대에 처리한 사람의 수

4. n명의 사람을 모두 처리 가능한 값이라면 answer을 update

   ※ 더 작은 범위에 처리가 가능한 경우가 있을 수 있으므로 return 하지 않는다.

풀이 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        
        //적어도 가장 빨리 처리하는 심사대가 1명 처리하는 시간 이상은 걸린다.
        long start = times[0]; 
        //최악의 경우는 가장 오래 걸리는 심사대가 모든 사람들을 처리하는 경우이다.
        long end = (long)times[times.length-1] * n;
        
        while(start <= end) {
            long mid = (start + end) / 2;
        
            //mid의 시간동안 몇 명의 사람을 처리할 수 있는지 확인   
            long sum = 0;
            for(int time : times) {
                sum += mid/time;
            }
            
            if(sum >= n) { // n명 이상의 사람을 처리 가능
                answer = mid;
                end = mid - 1;
            }
            else { // 더 많은 사람 처리 필요
                start = mid + 1;
            }
        }
        
        return answer;
    }
}