ps:problems:programmers:43238
입국심사
| ps | |
|---|---|
| 링크 | programmers.co.kr/… |
| 출처 | 프로그래머스 |
| 문제 번호 | 43238 |
| 문제명 | 입국심사 |
| 레벨 | Level 3 |
| 분류 |
파라메트릭 서치 |
| 시간복잡도 | O(nlog(km/n)) |
| 인풋사이즈 | n<=10^5, m<=10^9, k<=10^9 |
| 사용한 언어 | Python |
| 해결날짜 | 2021/06/29 |
| 태그 | |
풀이
- 원본은 COCI에 출제되었던 문제로, BOJ에도 동일한 문제를 번역한 것이 입국심사에 있다. 풀이는 그쪽을 참고.
코드
"""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)- Dependency: teflib.algorithm.binary_search
ps/problems/programmers/43238.txt · 마지막으로 수정됨: 2021/06/29 02:11 저자 teferi
토론