입국심사

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
 
        long left = 0;
        long right = (long) n * times[times.length - 1]; // 최대로 걸리는 시간
 
        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = 0;
 
            // mid 만큼의 시간동안 심사할 수 있는 사람의 수 계산
            for (int i = 0; i < times.length; i++) {
                sum += mid / times[i];
                if (sum >= n)
                    break;
            }
 
            if (sum < n) // 심사를 다 하지 못한 경우
                left = mid + 1;
            else // 심사를 다 한 경우
                right = mid - 1;
        }
        // 최소 시간은 left에 저장
        answer = left;
        return answer;
    }
}

문제의 카테고리가 이진 탐색임에도 불구하고 어떻게 할지 감이 잡히지 않았다.

0초부터 시작하여 n을 감소시키며 계산하여 최소 시간을 찾으려고 했지만 잘 되지 않았다.

이진 탐색을 통해 최대로 걸리는 시간부터 범위를 줄여나가는 방법으로 해결하였다.

 

해결 방법은 다음과 같다.

1. left와 right를 통해 mid를 정한다.

2. 해당 mid 시간에 처리할 수 있는 사람의 수를 구한다.

3. n 이상일 경우 right를 낮추고, n 미만일 경우 left를 높인다.

4. 최종적으로 얻어낸 최소 시간은 left에 저장된다.

 

참고 사이트 : https://youngest-programming.tistory.com/499