백준 3079 입국심사(이분탐색)

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

3079번: 입국심사

문제의 범위를 보고 이분탐색이라고 생각을 먼저 했다.

하지만 어떤값을 탐색할지에 대해 고민이 많았는데 결과적으로 우리가 구하려는 총 시간에 대해서 탐색한다.

일단 start, end값을 정해야하는데 0이나 1이라고 두고 end는 min(time) * m이 된다.

why?)

time에서 가장 작은 값의 입국심사대에 m명 모두 그 심사대만 이용가능한 경우이므로 min(time)*m 이 된다.

 

우리가 탐색하는 기준 : m명 모두 입국심사에 통과할 수 있는 최소의 시간

똑같이 이분탐색의 mid값을 정한다음에 그 값에 대해서 모든 입국심사대의 Tk로 나눠준다.

why?)

지금 mid값은 m명이 모두 통과할 수 있는 시간인데 각 입국심사대로 부터 mid // Tk로 나누게 되면

mid시간 동안 그 입국심사대에서 통과할 수 있는 인원의 수를 구할 수 있다.

 

이런식으로 모든 입국심사대에서 통과시킬 수 있는 모든 인원의 수를 더한다음 if temp < m이 되면 start를 증가시키고 if temp >= m이면 m명을 모두 통과 할 수 있다는 뜻이니까 end를 줄여나간다.

why?)

우리는 최소의 time을 구하는 것이기 때문에 end를 최대한 줄여나가서 start >= end가 되는 지점까지 찾아야한다. 그리고 time이 sorted가 되어있기 때문에 if temp >= m:에서 res값을 전의 res값과 비교해줄 필요 x

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
time = sorted(list(int(input()) for _ in range(N)))

start = 0
end = min(time) * M
result = 0

while start <= end :
    mid = (start + end) // 2
    temp = 0
    for t in time:
        temp += mid // t

    if temp >= M:
        end = mid - 1
        result = mid #sorted했기 때문에 min()해줄 필요 x
    else:
        start = mid + 1
    #print(start,end)
print(result)