이분탐색 - 입국심사(Lv.3)

• left = 1 # 최소 1
• right = max(times) * n # 최악의 경우: 가장 오래걸리는 심사관이 모든 인원을 처리하는 경우
• done_number += mid // time : 해당 심사관이 mid시간 안에 완전히 처리 가능한 인원수

def solution(n, times):

    
    left = 1 # 최소 1
    right = max(times) * n # 최악의 경우: 가장 오래걸리는 심사관이 모든 인원을 처리하는 경우
    
    while left < right: # left == right가 되기 전까지 탐색
        # mid: 현재 범위 시간의 중앙값, 최적 해 아님 주의
        mid = (left + right) // 2
        
        # 모든 심사관이 mid 시간 안에 처리 가능한 인원 수
        done_number = 0
        for time in times:
            # mid: 주어진 시간, time: 각 심사관이 1명 처리하는 데 걸리는 시간
            # mid를 time으로 나눈 몫: 해당 심사관이 mid시간 안에 완전히 처리 가능한 인원수
            done_number += mid // time
            
            # 이미 탐색 가능 인원이 n명 이상이라면 끝내기
            if done_number >= n:
                break
        
        if done_number < n: # mid 시간 안에 n명 처리 불가, 오른쪽 범위 안에서 탐색
            left = mid + 1
        else: # mid 시간 안에 n명 처리 가능, right = mid로 두고 더 작은 시간이 있는지 탐색
            right = mid
    
    
    return left # whlie이 끝난 left값이 최소 시간