[백준] 3079 입국심사 풀이 (Python)

문제 정보
문제 링크 : BOJ 3079 입국심사 
문제 난이도 : 골드 5
유형 : 이분탐색 / 매개변수 탐색

 

1. 문제 접근

이 문제는 전체 심사를 끝내는 데 필요한 최소 시간을 찾는 문제이기 때문에
“특정 시간 t 안에 m명을 처리할 수 있는가?”를 판단하는 형태로 재정의했다.

 

어떤 값을 기준으로 이분 탐색하는가? → 시간(time)

결과적으로 우리가 구하고 싶은 값이 “최소 시간” 자체이므로
탐색의 기준값을 시간(time)으로 두는 것이 가장 자연스럽다.

 

또한 시간이 커질수록 처리할 수 있는 인원 수가 증가하기 때문에
‘가능 / 불가능’을 단조적으로 분리할 수 있어 이분 탐색이 성립한다.

 

어떤 값을 비교해야 하는가? → t 시간 동안 처리 가능한 총 인원 수

특정 시간 t를 가정했을 때,
각 심사대는 t // 심사시간만큼 사람을 처리할 수 있다.

 

이를 모두 합산하면
t 시간 동안 처리 가능한 전체 인원 수가 되고,
이 값이 m 이상이면 t 시간 안에 모든 사람을 처리할 수 있는 것이다.

• 총 처리량 ≥ m → t는 가능 → 더 작은 시간을 탐색
• 총 처리량 < m → t는 불가능 → 더 큰 시간을 탐색

따라서 이 문제는 정확한 값을 직접 찾는 게 아니라,
시간 t에서 “조건을 만족하는지”만 판단하여 탐색 범위를 줄여가는 구조다.

 

 

왜 이분 탐색 + 매개변수 탐색인가?

이 문제에서 구해야 하는 값은 모든 사람을 심사하는 데 필요한 최소 시간이다.

시간의 최댓값은 min(times) * M 으로 최대 10¹⁸까지 커질 수 있어,
시간을 하나씩 증가시키며 정답을 찾는 방식이나 완전 탐색 방식은 사용할 수 없다.

 

또한 시간 t가 주어졌을 때, 각 심사대가 t 동안 처리할 수 있는 사람 수는
t // time 으로 바로 계산할 수 있으며 이를 모두 합산하면
t 시간 안에 M명을 처리할 수 있는지 확실하게 판단할 수 있다.

 

이처럼

• 정답이 되는 값이 “시간”이라는 하나의 숫자이고
• 그 값이 주어졌을 때 가능한지/불가능한지를 판단할 수 있으며
• 가능한 시간과 불가능한 시간이 명확하게 구분되기 때문에

넓은 시간 범위 안에서 정답 후보를 빠르게 줄여가는
이분 탐색 기반의 매개변수 탐색 방식이 가장 효율적이다.

 

 

2.풀이 코드 (Python)

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
times = [int(input()) for _ in range(N)]
# 오름차순 정렬
times.sort()

# 총 심사 시간 기준으로 이분탐색 

left = 0
# 가장 많이 걸리는 경우 : 최소 시간 * M 
right = min(times) * M

while left < right :
    mid = (left + right) // 2
    # 각 심사대 별로 수용 가능한 인원 확인 
    total = sum([mid//time for time in times])
    
    # 인원을 수용하지 못하면
    if total < M :
        left = mid +1
    else : 
        right = mid

print(right)

 

 

3. 회고

처음에는 가능한 경우에도 right = mid - 1로 범위를 줄였는데, 이렇게 하면 mid가 실제 정답일 수 있는 상황에서도

mid를 바로 범위 밖으로 밀어내는 문제가 생겼다.

 

그래서 두 번째 테스트 케이스에서 올바른 결과가 나오지 않았다.

 

이 문제는 특정 시간 mid가 실제 정답인지 즉시 결정할 수 있는 구조가 아니라, mid가 가능한지만 확인할 수 있는 형태다.

가능한 경우에는 mid 자체가 정답이 될 수 있으므로, mid를 제외하지 않고 그대로 포함한 범위에서 탐색을 이어가야 한다.

 

이번 풀이를 통해, 이분 탐색에서도 정답 후보를 어떻게 유지하고 갱신해야 하는지를 더 명확하게 생각할 수 있게 되었다.