[Programmers] 입국심사 python3

문제보러가기

- https://school.programmers.co.kr/learn/courses/30/lessons/43238

풀이

• 이 문제는 입국심사를 기다리는 사람이 1,000,000,000 명인 경우를 고려해 이진 탐색 방법을 떠올려야한다.
• 10억인 경우를 완전탐색 할 수 없다. 이진 탐색을 할경우 O(log2(N))으로 약 30 번만에 탐색이 가능하다.
• 우리가 찾으려는 시간은 주어진 심사대를 모두 사용하여 가장 빨리 입국심사를 마무리할 수 있는 시간이다.
• 따라서, 가장 빠른 시간을 찾기 위해서는 각 심사대에서 처리한 사람수의 합이 주어진 n과 같아지는 경우를 찾아야 한다.
• 이를 코드로 구현하면 boared += mid//time으로 식을 세우고, 이를 만족하는 경우를 찾아 이진 탐색을 하면 된다.

코드

def solution(n, times):
    answer = 0

    left = 0
    right = max(times)*n

    while left <= right:
        mid = (left + right) // 2
        boarded = 0
        for time in times:
            boarded += mid//time
        if boarded >= n:
            right = mid - 1
        else:
            left = mid +1
    answer = left
    return answer