| ps | |
|---|---|
| 링크 | programmers.co.kr/… |
| 출처 | 프로그래머스 |
| 문제 번호 | 43238 |
| 문제명 | 입국심사 |
| 레벨 | Level 3 |
| 분류 |
파라메트릭 서치 |
| 시간복잡도 | O(nlog(km/n)) |
| 인풋사이즈 | n<=10^5, m<=10^9, k<=10^9 |
| 사용한 언어 | Python |
| 해결날짜 | 2021/06/29 |
| 태그 | |
"""Solution code for "Programmers 43238. 입국심사".
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43238
- Solution link: http://www.teferi.net/ps/problems/programmers/43238
"""
from teflib import algorithm
def solution(n, times):
def is_possible(total_time):
checkable_passenger_count = sum(total_time // time for time in times)
return checkable_passenger_count >= n
upper_bound = max(times) * (len(times) // n + 1)
return algorithm.binary_search(0, upper_bound + 1, is_possible)