백준 3079번: 입국심사 (G5) - Python 풀이

안녕하세요.
시간이 없으니 바로 Let's go

문제 설명

https://www.acmicpc.net/problem/3079

여행을 갔답니다.
사람은 M명, 입국심사대는 N개입니다.
k번 심사대의 심사관의 심사 시간은 Tk입니다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

• 입력
  • 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)
  • 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)
• 출력
  • 첫째 줄에 모든 사람들이 심사를 마치는 데 걸리는 시간의 최솟값을 출력한다.

예제 입력 1

2 6
7
10

예제 출력 1

28

풀이 과정

이것도 2시간을 풀었는데 1시간 됐을 때 제출한 코드랑 거의 똑같습니다.
이분 탐색은 다 if ? > ?: ~ / elif ? < ?: ~ / else: ~ << 이런 식으로 3개의 조건으로 분리될 것이라 추측한 저의 고정관념을 깨준 문제입니다.

# 빠른 입력
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
T = [int(input()) for _ in range(N)]

# 특정 시간일 때 심사를 마친 사람이 몇 명인지 반환하는 함수
def calculate_finished_person_num(time):
    finished_person_num = 0
    # 특정 시간의 값 time을 각 심사대의 심사시간 t로 나눈 몫의 합
    for t in T:
        finished_person_num += (time // t)
    return finished_person_num

# 이분탐색의 범위 설정
left = min(T)
right = max(T) * M
# 최악의 시간으로 초기화
answer = right

# 반으로 쪼갤 수 있는 범위면 반복
while left <= right:
    # 범위의 중간 시간
    mid = (left + right) // 2
    # 중간 시간일 때 몇 명의 사람이 심사를 마쳤는가
    finished_person_num = calculate_finished_person_num(mid)
    # M명보다 많거나 같다면
    if finished_person_num >= M:
    	# 일단 지금 시간 answer에 저장해두고
        answer = mid
        # 시간의 최댓값을 줄여서 더 최소의 시간이 없는지 확인
        right = mid - 1
    # M명보다 적다면
    else:
    	# 시간의 최솟값을 키운다
        left = mid + 1

# M명이 심사받는 데 걸리는 최솟값 출력
print(answer)

범위를 계속 좁혀가면서 중간값을 구하고, 특정 시간에서 문제가 원하는 M명이 충족되었어도, M명을 충족하는 더 최소의 시간이 있을 수 있기 때문에 answer에 저장해두고 다시 확인하는 부분이 포인트였던 문제였습니다.