[BOJ] 3079. 입국심사(Python) / Binary Search

3079번: 입국심사

입국 심사대의 개수 N과, 심사를 받을 인원 M이 주어지고, 각 입국 심사대의 심사에 걸리는 시간이 주어질 때 모든 인원이 심사를 받는 최소 시간을 구하는 문제

• 사용 알고리즘 : 이분 탐색 Binary Search
• 최소, 최대 시간을 left, right라 두고 그 중간값을 mid로 하여
• 전원 total 이 입국심사 가능한 시간이라면 mid-1를 right로 최대 시간을 줄여 다음 턴 때의 탐색 범위를 좁힌다.
• 불가능하다면 left를 mid + 1로 최소 시간을 늘려 다음 턴 때 탐색의 최소 시작값을 키워 다음 턴 때의탐색 범위를 좁힌다.
• 조건 left <= right가 성립되는 순간 while문을 탈출한다.
• 그 때까지 범위 좁히면서 mid값에 대해 answer과 mid를 비교해 최솟값을 갱신한다.
• 최종으로 갱신된 최솟값 answer를 출력한다.

 

파이썬 코드는 다음과 같다

---

from sys import stdin
input = stdin.readline

N, M = map(int, input().split())
time = [int(input()) for _ in range(N)]

left = min(time)                    # 최소 시간
right = answer = max(time) * M      # 최대 시간

while left <= right:
    total = 0       			# mid 시간 동안 검사할 수 있는 총 사람의 수
    mid = (left + right) // 2		# 중간값으로 검사
    for i in range(N):      		# 입국심사대별로 검사
        total += mid // time[i]
        if total >= M:			# 이미 M명 이상 검사 할 수 있다면 가능하므로 break
            break
    if total >= M:          		# 검사할 수 있는 총 사람 수가 M보다 크면 가능한 경우
        right = mid - 1     		# 오른쪽에서 범위 좁히기
        answer = min(answer, mid)   	# 최솟값 갱신
    else:
        left = mid + 1      		# 왼쪽에서 범위 좁히기

print(answer)

---

• 시간 : 212ms / 메모리 : 123736kb
• 고찰 : 실버 문제지만 꽤 어려웠다ㅠㅠ 이분탐색을 생각해내기도 쉽지 않았다. 사실 혼자 풀다가, 잘 안 돼서 다른 분의 코드를 보고 풀었다.. 코드를 본 순간 금방 이해가 됐다. 이분 탐색은 여러 번 풀어봤지만, 뭔가 아직도 어렵다.. 그래도 많이 풀다보면 쉽게 푸는 날이 오겠지! Keep Going 하자.