[Baekjoon 3079 / Python / 골드5] 입국심사

문제

 

 

이분 탐색 문제이다. 일반적인 이분 탐색의 틀에서 크게 벗어나지 않는다.

다만 start와 end의 초기 설정 및 mid값의 유효성을 어떻게 판단할지에 대해서 고민이 좀 필요했다.

 

 

# 이분 탐색

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

test = [int(input()) for _ in range(N)]

# 이분 탐색

def binarySearch():

    start = min(test)

    end = max(test) * M

    result = end

    while start <= end:

        mid = (start + end) // 2

        total = 0

        # 임의의 시간(mid) 동안 몇명을 심사하는지 계산

        for i in range(N):

            total += mid // test[i]

        # 전부 또는 더 많이 심사했을 경우

        if total >= M:

            end = mid - 1

            result = min(result, mid) # 최적의 답을 갱신한다

        # 덜 심사했을 경우      

        else:

            start = mid + 1

    return result

print(binarySearch())

 

 

start는 가장 짧은 심사시간, end는 가장 긴 심사시간 * M(인원수)로 설정했다. 어떤 테스트 케이스가 들어와도 이 시간보다 짧거나 길 수 없기 때문이다.

start와 end의 범위는 반드시 모든 경우의 수를 포함하도록 잘 생각해서 설정하는 것이 중요하다.

 

mid의 유효성 판별은, mid를 각 심사시간으로 나눈 값들을 모두 더해서 특정 mid시간동안 몇 명을 심사할 수 있는지를 계산했다. 

예를 들어 심사대가 [2, 5, 7] 이 있다면 20초간 심사할 수 있는 사람의 수는,

20 // 2 -> 10

20 // 5 -> 4

20 // 7 -> 2

10 + 4 + 2 -> 총 16명을 심사할 수 있다. 

이렇게 계산하면 특별한 예외상황 없이 정확하게 심사하는 인원수를 구할 수 있다.

 

문제에서는 "어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지" 라던가, "항상 이동을 해야 하는 것은 아니다" 라던가, "바로 심사받지 않고 기다렸다가 다른 심사대로 가면 더 빠를 수 있다" 이런 문구들이 나오는데 전혀 신경 쓸 필요가 없다. 헷갈리게만 할 뿐이다.

 

 

결과