[3079] 입국 심사 in python

 

 

 

문제에서 주어진 예시를 토대로

돌아가는 방식을 이해하기 위해 위와 같이 그림을 그려봄.

 

입국심사대가 1개일 경우에는 반복문을 돌릴필요 없이

m명을 곱해주면 된다.

 

입국심사대가 여러 개 일 경우가 문제이다.

 

이분 탐색 문제라고는 생각도 못했는데

이분탐색을 이용하여 푸는 문제였다 0_0 ! 

 

 

내가 생각했던 방식으로 구현하려고 하니

머리가 지끈거렸는데

이분 탐색을 이용하면

쉽게 구할 수 있었다 ㅎ ..

 

cnt=0

for time in Times:

cnt+=mid//time

 

-> 이 식을 이용하면 되는데

이 식을 떠올리지 못했다... 흑

 

n=2, m=6

Times=[7,10]의 예시로 들어보면

일단 최솟값은 28초이다.

 

mid를 28초라고 치자.

위 반복문이 돌아가는 걸 확인하면

28//7 = 4

28//10 = 2

 

4+2=6명!

m이랑 같은 값이 나온다.

 

 

28//7은

28초 동안 7초 걸리는 입국 심사대에서

검사를 받을 수 있는 사람의 수가 4명이라는 뜻이고,

 

28//10은

마찬가지로 28초 동안에 10초가 걸리는 입국 심사대에서

검사를 받을 수 있는 사람의 수를 의미한다.

 

 

나는 처음에 그림을 그릴 때

입국 심사대가 여러개면

동시간대에 검사하는 사람의 수가 여러 명이 된다는 소리인데

이걸 동시에 어떻게 처리를 해야할까?라는 생각이 들었다.

 

 

( 총 시간// 입국심사대 걸리는 시간 ) 의 식을 이용하게 되면

총 시간동안 해당 입국심사대에서

검사를 받을 수 있는 사람들의 수를 구할 수 있게 된다.

 

문제에서 주어진 대로라면

동시간대에 여러 입국 심사대에서 검사를 받을 수 있는 거니까

 

총 시간동안 해당 입국심사대에서

각각 몇 명씩 검사를 진행해줄 수 있는지만 확인하고

그 수를 다 더한 값이 m값과 같아야한다.

 

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
T = [int(input().rstrip()) for _ in range(n)]
left = 0
right = min(T) * m
result = right

if n == 1:
    result = T[0] * m
    print(result)
else:
    while left < right:
        mid = (left + right) // 2
        cnt = 0
        for t in T:
            cnt += mid // t

        if cnt < m:
            left = mid + 1
        else:
            result = min(mid, result)
            right=mid
    print(result)