3079. 입국심사 (Python)

3079번: 입국심사

 

풀이

 친구들이 심사를 마치는데 걸리는 시간에 대해 이분탐색을 하여 해결할 수 있다. left와 right를 설정하고 mid를 구하여 mid초에 대해서 각 심사대에서 몇 명을 심사할 수 있는지를 체크하여 상근이와 친구들의 수인 M보다 클 경우 답을 갱신해주면 된다. 

 

코드

if __name__ == '__main__':
    N, M = map(int, input().split()) # N: 입국심사대 총 개수, M: 상근이와 친구들의 수
    times = []

    for i in range(N):
        times.append(int(input()))

    left = 1
    right = 1_000_000_000_000_000_000

    res = 0

    while left <= right:
        mid = (left + right) // 2

        tmp = 0 # 현재 시간(mid)에 대해서 심사할 수 있는 사람의 수
        for time in times: # 각 심사대에서 몇 명을 심사할 수 있는지 체크
            tmp += mid // time

        if tmp >= M: # M 이상 심사할 수 있으면 답 갱신
            res = mid
            right = mid - 1
        else:
            left = mid + 1

    print(res)