[백준] 3079번: 입국심사(이분탐색, Python)

문제 링크

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

3079번: 입국심사

 

풀이

풀이 설명

* 분류: 이진탐색

• 인원수가 10억명, 시간도 10억초 까지의 범위이므로 이진탐색을 떠올린다.
• 대체로 이진 탐색의 기준이 되는 건 구하고 싶은 변수이다. 
• 지금은 시간을 출력하는 것이므로 기준을 시간(초)로 잡는다. 
•  검사대 시간 배열 -> info
• 시간을 기준으로 한다면 start = 가장 짧은 검사대 시간, end = (가장 긴 검사대 시간 * 사람 인원수) 로 하겠다.
• mid 값은 총 시간을 의미한다. 
•  따라서, mid 시간일때 각 검사대가 동시에 검사를 진행하는 경우 최대 인원수가 m명 이상인 경우를 구하면 된다. 
  • 각 검사대에서 mid시간 안에 검사할 수 있는 인원 수 : mid // 검사대 시간(info[i])
• 이때 가장 최소 값의 mid값이 답이 된다. 

 

풀이 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
info = []
for _ in range(n):
    info.append(int(input()))

info.sort()

s = info[0]
e = info[-1] * m #최대 시간 * 인원수
ans = e
while s <= e:
    mid = (s + e)//2
    total = 0

    for i in range(n):
        total += mid // info[i]

    if total < m:
        s = mid + 1
    else: # total >= m
        e = mid - 1
        ans = min(ans, mid)

print(ans)