사용자 도구

사이트 도구


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
태그

고득점 Kit - 이분탐색

풀이

  • 원본은 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)

토론

댓글을 입력하세요:
J P C T A
 
ps/problems/programmers/43238.txt · 마지막으로 수정됨: 2021/06/29 02:11 저자 teferi