입국심사 (lv3)

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

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

---

 가장 먼저 눈에 들어오는 것은 대기자가 최대 10억 명에 각 심사관의 심사 시간이 최대 10억 분이라는 것이다. 따라서 한명 한명 가장 본인의 대기시간이 적게 걸리는 부스를 선택하는 방식은 쓸 수 없다.

 이 문제에서의 핵심은 각 심사관들은 어찌됐건 자신의 심사 시간에 한 명씩 밖에 심사하지 못한다는 것이다. 너무나 당연한 사실이지만, 특정 시간까지 각 심사관은 자신이 소화할 수 있는 분량만 소화 가능하다는 점을 깨닫는게 중요한 것이다. 조건에 의해 대기자들은 심사대를 선택해서 줄을 설 수 있기 때문에, 다시말해 "줄을 어디에 반드시 서야한다는" 조건자체가 없기 때문에 이 문제는 단순히 특정 시간까지 각 부스가 소화 가능한 업무량을 더해준 뒤 목표치인 n과 비교해주면 된다.

 예를 들면 대기자가 11명이고, 각 심사대의 한 명당 소요시간이 [4, 5, 7, 7, 8]로 주어진다고 하자. 모든 사람들이 가장 시간이 오래걸리는 마지막 심사대에 줄을 선다고 가정하면, 소요시간은 총 8*11 = 88분이 될 것이다. 최소시간을 1분이라 했을 때 중간 값인 44분까지 각 부스가 소화 가능한 업무량을 더하면, 11+8+6+6+5=36, 총 36명이 된다. 이는 목표치인 11명보다 터무니 없이 많으므로, 우린 36분보다 적은 시간으로 해낼 수 있다는 것을 알 수 있다. 이런식으로 이진 탐색을 진행하면 답을 얻을 수 있다. 

코드

def solution(n, times):
    answer = 0
    times.sort()
    length = len(times)
    start = 1
    end = (n-length+1)*times[-1]
    
    while start < end:
        mid = (start + end) // 2
        s = 0
        for time in times:
            s += mid // time
        
        if n > s:
            start = mid + 1
            answer = start
        else:
            end = mid
    
    return answer