입국심사

• 프로그래머즈의 입국심사과 동일한 문제이다.
  • 동일한 이유는 둘다 동일한 COCI 문제를 번역한 것이기 때문이다. 입국심사대에 10억명이 몰리는 원본 문제 자체도 이미 비현실적이긴 하지만, BOJ번역에서는 친구가 10억명이 있고, 모두 비행기 한 대에 타고서 놀러간다는 설정이 되어버렸다.
• 풀이는 파라메트릭 서치를 통해서 풀면 된다. 주어진 T시간 동안 심사를 받을수 있는 사람의 수가 M 이상인지 계산하는 함수를 만들고, 그 함수가 true가 되는 T의 최솟값을 찾으면 된다. 주어진 T시간 동안 심사를 받을 수 있는 사람의 수는 각 심사관이 T시간동안 몇명을 심사할수 있는지 계산해서 더하면 되므로 O(n).
• T값의 탐색 범위의 상한은 가능한 최댓값보다 크도록 적당히 잡아주면 되는데, 이럴때 내가 주로 쓰는 방법은, '가장 빠른 심사관 한명이서 모든 사람을 심사하는 경우의 시간 = min(T)*M' 또는 '모든 심사관이 동일한 수의 사람을 심사하는 경우의 시간 = max(T)*ceil(M/N)' 이다. 더 타이트한 바운드를 잡으면 그게 물론 좋기야 하지만, 어차피 로그 안에 들어가는 텀이라서 영향이 그렇게 크지는 않다. 그러면 그냥 심플한 값을 찾는 것이 낫다.
• 바운드를 max(T)*ceil(M/N) = O(km/n) 으로 잡으면 총 시간복잡도는 O(nlog(km/n)).

"""Solution code for "BOJ 3079. 입국심사".

- Problem link: https://www.acmicpc.net/problem/3079
- Solution link: http://www.teferi.net/ps/problems/boj/3079

Tags: [Binary search]
"""

import sys
from teflib import algorithm


def main():
    def is_possible(total_time):
        checkable_passenger_count = sum(total_time // t_k for t_k in T)
        return checkable_passenger_count >= M

    N, M = [int(x) for x in sys.stdin.readline().split()]
    T = [int(sys.stdin.readline()) for _ in range(N)]

    print(algorithm.binary_search(0, min(T) * N, is_possible))


if __name__ == '__main__':
    main()

• Dependency: teflib.algorithm.binary_search