문제

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

---

입력

입국심사를 기다리는 사람 수 n
각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times

---

출력

모든 사람이 심사를 받는데 걸리는 시간의 최솟값

---

풀이

제한조건

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

접근방법

수의 범위가 매우 크다.
적절한 시간을 찾아야 하는데, 단순하게 탐색해서는 시간내에 찾을 수 없다.
이분 탐색을 통해 반으로 줄여가며 정답을 찾아야 한다.

(이분탐색 : https://velog.io/@hyeokkr/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89)

특정 시간을 기준으로 완료된 사람 수를 파악하는 방법은
각 심사위원들의 심사시간으로 나눈 몫을 통해 알 수 있다.

심사를 통과한 사람 수 
= 현재시간 / 1번 심사관의 심사시간 
+ 현재시간 / 2번 심사관의 심사시간 
+ ...
+ 현재시간 / N번 심사관의 심사시간 

주의해야할 점은 Type 이다.
주어진 매겨변수가 모두 int type이기 때문에
Type Casting이 필요하다.

또한 int의 범위로 충족시킬 수 있는 값이 없다는 점도 반드시 주의해야 한다.

---

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) { 
        Arrays.sort(times);
        int len = times.length;
		long min = (long)n * times[0] / len;
		long max = (long)n * times[len - 1];
        while(min <= max){
            long count = 0;
            long mid = (min + max) / 2;
            // mid 시간 기준으로 완료된 사람 수를 구한다.
            for(int i : times){
                count += mid / i;
            }
            // 완료된 사람이 부족한 경우 재 탐색
            if(count < n){
                min = mid + 1;
            }else{
                // 완료된 사람이 많은 경우, 시간이 너무 많이 주어진 경우
                // 줄 일 수 있는 최대로 줄인다.
                max = mid - 1;
            }
        }
        return min;
    }
}