백준 3079번 : 입국심사

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

3079번: 입국심사

2110번에서 알게된 내용들을 적용해서 생각보다 쉽게 푼 문제다.

 

 M명의 사람들은 입국하기위해 입국심사를 받는다. 심사대는 총 N개가 있고 심사대마다 심사에 소요되는 시간이 정해져있다. M명의 사람들을 모두 통과시키는 최소한의 시간을 구하는 문제이다.

 

 앞서 푼 문제에서 배운 이분 탐색의 요령을 그대로 적용했다. 구하려는 값은 시간이기 때문에 가능한 범위 안에서 조건(시간 안에 사람들이 모두 통과할 수 있는지)을 만족시키는 최소한의 시간을 구한다. 이때 최소화된(최적화된) 시간은 심사시간이 가장 짧은 심사대로 M명의 사람이 모두 통과하는데 걸리는 시간보다 짧거나 같다. 그 범위 안에서 시간을 늘리거나 줄여가며 적절한 시간을 찾을 것이다.

(자료형에 따라 M의 최대가 10억, 심사 시간의 최대가 10억이기 때문에 그냥 10억의 제곱을 끝 범위로 정해도 상관없을 것 같다.)

 

 이제 주어진 시간 안에 최대 몇명이 심사를 통과할 수 있는지 계산해본다. 주어진 시간보다 심사가 오래 걸리는 심사대는 고려할 필요가 없다. 주어진 시간을 한 심사대의 심사시간으로 나눈 몫이 그 심사대에서 시간 안에 통과시킬 수 있는 최대 인원 수이므로, 모든 심사대에서 통과시킬 수 있는 인원의 합과 우리가 통과시켜야 하는 인원(M)과 비교한다. 통과 인원이 적으면 시간이 더 필요한 것이고, 통과 인원이 같거나 많으면 시간을 줄이며 조건을 만족시키는 최소값을 찾는다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
t = sorted([int(input()) for _ in range(n)])
s, e, r = 1, t[0] * k, 0

while s <= e:
    m = (s+e)//2
    cnt = sum([m//i for i in t])

    if cnt >= k:
        e = m-1
        r = m
    else:
        s = m+1
print(r)