SWEA: 3074 입국심사

문제

SW Expert Academy

 

문제 풀이

 M명의 사람이 입국심사를 받으려고 할 때, 입국 심사의 소요 시간이 최소가 되는 시간을 출력하는 문제이다. 문제를 풀기 위해서는 `이분 탐색`을 통해, 심사가 가능한 최소 시간을 구할 수 있다. 이 문제에서 이분 탐색의 `mid` 값은 입국 심사하는데 소요되는 전체 시간을 의미한다. 예를 들어 `mid`가 30초라면 30 // 심사하는데 걸리는 시간을 구하게 되면 입국할 수 있는 사람 수가 결정되게 된다.

 

코드

T = int(input())

for test_case in range(1, T + 1):
    answer = 0
    n, m = map(int, input().split())

    times = [int(input()) for _ in range(n)]
    left, right = 1, max(times) * m

    while left <= right:
        mid = (left + right) // 2
        people = sum([mid // time for time in times])

        if people >= m:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print('#' + str(test_case), answer)