EunSung.log

입국심사

2 min read

문제 정보

풀이

이진 탐색을 활용하는 문제다. (파라메트릭 서치)

문제를 “명이 심사받는 데 걸리는 최소 시간”을 구하는 게 아니라 “분에 명을 심사하는 게 가능한가?”를 구하는 문제로 바꿔서 생각한다.

가불가 판단을 위해선 분 동안 최대로 심사받을 수 있는 사람의 수를 구해야 하는데, 이는 의 합으로 구할 수 있다.

심사관 한 명이 한 사람을 심사하는 데 times[i]분이 걸린다고 하면, t분 동안 이 심사관이 심사할 수 있는 최대 인원은 t / times[i]명이다. (정수 나눗셈이므로 소수점 이하는 버린다.)

각 심사관은 독립적으로 병렬 심사하므로, 전체 심사 가능 인원은 각 심사관의 심사 가능 인원을 단순히 합산하면 된다. 이 합이 이상이면 분 안에 명을 심사하는 것이 가능하다.

코드

import java.util.*;
 
class Solution {
    public long solution(int n, int[] times) {
        long low = 1;
        long high = (long) 1e14;
        long answer = high;
        
        while (low <= high) {
            long mid = (low + high) / 2;
            
            if (isPossible(mid, n, times)) {
                answer = Math.min(answer, mid);
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
        
        return answer;
    }
    
    private boolean isPossible(long t, int n, int[] times) {
        long max = 0;
        
        for(int time : times) 
            max += t / time;
        
        return max >= n;
    }
}

백링크