[프로그래머스] 입국심사

문제

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

제한사항

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

풀이

이분법

코드

def solution(n, times):
    answer, m = 0, len(times)
    begin, end = 0, n * max(times)
    while begin <= end:
        mid = (begin + end) // 2
        
        pN = 0
        for i in range(0, m):
            pN += mid // times[i]
        
        if pN < n: begin = mid + 1
        else:
            end = mid - 1
            answer = end
    
    return begin