[Python] programmers 입국심사

1. 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

2. 문제 요약

모든 사람이 심사를 받는데 걸리는 시간 최솟값 구하기

3. 아이디어 정리

1. 이분 탐색을 통해 걸리는 예측 시간을 구한다.
2. 해당 예측 시간으로 몇 명이 허용되는지 확인
3. 허용 가능한 인원으로 left, right 값을 조절

 

4. 문제 풀이

4-1. 내 풀이

def solution(n, times):
    answer = 0
    left = 0
    right = max(times) * n

    while left <= right:
        mid = (left + right) // 2     # 걸리는 예측 시간
        all_ = 0                      # 해당 시간 동안 몇 명이 허용되는지 확인
        for time in times:
            all_ += mid // time
        if all_ < n:
            left = mid + 1
        elif all_ >= n:
            answer = mid
            right = mid - 1
    return answer

 

 

5. 결론

• 이분 탐색