[programmers/python] 입국심사 문제 풀이 - 이분 탐색(Parametric Search)

 

문제 설명

• url : https://school.programmers.co.kr/learn/courses/30/lessons/43238
• n: 심사를 받아야 하는 사람 수이다.
• times: 각 심사관이 한 사람을 처리하는 데 걸리는 시간 목록이다.

 

모든 사람이 심사를 마치는 데 걸리는 최소 시간을 구하는 것이 목표이다.

---

핵심 아이디어

어떤 시간 t가 주어졌을 때, 그 시간 동안 각 심사관이 처리할 수 있는 사람 수는 t // time으로 계산할 수 있다. 모든 심사관의 처리 가능 인원을 더하면, t분 동안 총 몇 명을 처리할 수 있는지 알 수 있다.

total = sum(t // time for time in times)

이제 이 값을 기준으로 시간 t를 이분 탐색하며, n명 이상을 처리할 수 있는 가장 작은 t를 찾는 방식이다.

---

코드

def solution(n, times):
    l = 1
    r = max(times) * n
    ans = r

    while l <= r:
        m = (l + r) // 2
        total = sum(m // t for t in times)

        if total >= n:
            ans = m
            r = m - 1
        else:
            l = m + 1

    return ans

---

예시

n = 6
times = [7, 10]

• 28분이면 6명 모두 심사를 받을 수 있다.
• 이분 탐색을 통해 최소 시간을 찾으면 정답은 28이다.