[백준/파이썬] 3079: 입국심사

문제 보러 가기!!

풀이🤗

이분 탐색!!! 으로 풀었다.
이분 탐색에서 구하는 값은 '총 심사하는 데 걸리는 시간' 즉 ans 이다.
최솟값은 1, 최댓값은 (가장 짧은 심시 시간 X 심사할 사람의 수)로 했다.
그 시간을 구한 뒤에, 그 시간 동안 상근이와 친구들이 모두 심사 받을 수 있는지 봤다. (calculate_screening_cnt 함수)
모두 심사받을 수 있다면 답이 될 수 있는 건데, 더 짧은 시간에 심사 받을 수도 있기 때문에 return을 하지는 않았다.
모두 심사받을 수 없다면, 이 값을 늘려줘야 한다.

코드❤️

import sys

input = sys.stdin.readline

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

left = 1
right = min(times) * M
ans = right


def calculate_screening_cnt(time: int) -> int:
    """심사관들이 time초 동안 몇 명을 심사할 수 있는지 구하는 함수"""
    cnt = 0
    for i in times:
        cnt += (time // i)
    return cnt


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

    can_screening_cnt = calculate_screening_cnt(mid)
    if can_screening_cnt < M:
        left = mid + 1

    else:
        ans = min(ans, mid)
        right = mid

print(ans)