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

 

 

 

 

 

# 이분탐색
# 심사대 n개 사람수 m명 시간 t
# 탐색 범위는 심사에 걸리는 시간. t의 최소값 / 최대값 * 인원수 

import sys
n, m = map(int, input().split())
t = [int(sys.stdin.readline()) for _ in range(n)]
start, end = min(t), max(t) * m
result = end # 탐색을 진행하며 더 작은 값을 찾아가기때문에 현재 최대값으로 초기화해줌

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

    for i in range(n): # 중간값을 기준으로 각 심사대가 몇명이나 심사할수있는지 계산하여 합을 구함
        total += mid // t[i]

    if total >= m: # 만약 심사할수있는 사람이 m보다 크다면 = 탐색할 범위의 값을 줄여야함
        end = mid - 1
        result = mid # 중간값을 결과에 갱신
    else: # 심사할 수 있는 사람이 m보다 작다면 = 탐색 범위의 값을 늘려야함 
        start = mid + 1
print(result)

 

 

 

 

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