백준, 입국심사, 3079, 파이썬

[유형]

이분탐색

 

[문제링크]

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

 

[요약]

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

 

[문제풀이]

end : M명이 입국 심사를 하는데 걸리는 최대 시간. T_K의 최댓값이 10^9이므로, 10^9*M으로 초기화한다.

mid: 임의의 입국 심사하는데 걸리는 시간.

cnt: mid 동안 입국심사할 수 있는 사람의 수

cnt>=M: 상근이와 친구들의 수보다 입국심사할 수 있는 사람의 수가 많다는 것으로, 임의의 입국심사하는데 걸리는 시간을 줄인다.

반대의 경우, 임의의 입국심사하는데 걸리는 시간을 늘린다.

import sys
from collections import Counter
def input():
    return sys.stdin.readline().rstrip()

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

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

start = 0
end = 1000000000 *N

while start <= end:
    cnt = 0
    mid = (start + end) // 2

    for time in times:
        cnt += mid//time

    if cnt >= M:
        end = mid-1
    else:
        start = mid+1

print(start)