ETC/Algorithm
백준, 입국심사, 3079, 파이썬
coding_genie
2024. 9. 6. 01:35
[유형]
이분탐색
[문제링크]
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)