프로그래머스 - 입국심사

이분탐색의 구조

이 문제는 정수 범위 위의 단조 불리언 함수(monotonic boolean function)를 기반으로 한다.
수학적으로 이분탐색이 정확히 작동할 수 있는 구조 위에 놓여 있다.

1. 문제 정의

• 심사관은 여러 명 존재한다
• 각 심사관은 time[i]분마다 1명씩 심사 가능하다
• 사람 수는 n명이다
• 목표: 모든 사람이 심사를 마치기 위한 최소 시간 t를 구하라

2. 함수 정의

시간 t가 주어졌을 때, 각 심사관이 처리할 수 있는 인원을 모두 더하면
다음과 같은 함수 f(t)를 얻는다.

$$f(t)=\sum _{i=1}^m\lfloor \frac{t}{\text{time}[i]}\rfloor$$

이 함수는 단조 증가 함수이다.
즉, t가 커질수록 처리 인원은 절대 줄지 않는다.

3. 명제 정의

우리는 다음과 같은 참/거짓 명제를 생각할 수 있다.

$$P(t):=(f(t)\ge n)$$

이 명제는 t가 증가할수록 False → True로 바뀐다.
즉, 단조 불리언 함수이며, 한 번만 상태가 바뀐다.

목표는 P(t)가 처음으로 True가 되는 가장 작은 t를 찾는 것이다.

4. 이분탐색이 가능한 이유

이분탐색은 다음 조건을 만족할 때 사용할 수 있다:

• 정수 범위 t ∈ ℕ
• P(t)는 단조 불리언 함수 (False → True)
• 우리는 min { t | P(t) = True } 를 찾고자 한다

즉, "논리 명제의 최소 참 구간"을 찾는 탐색이 된다.

아래는 이를 구현한 이분탐색 알고리즘이다.

def solution(n, times):
    left, right = 1, max(times) * n
    while left <= right:
        mid = (left + right) // 2
        people = sum(mid // t for t in times)
        if people >= n:
            right = mid - 1
        else:
            left = mid + 1
    return left