입국심사 - Python, 이진탐색

 

 

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

프로그래머스

 

 

코드 & 풀이

 

def solution(n, times):
    left = 1
    right = max(times) * n
    
    answer = right
    
    while left <= right:
        mid = (left + right) // 2
        total = sum(mid // time for time in times)
        
        if total >= n:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    
    return answer

 

 

right를 최악으로 가정

 

최악 = 심사가 가장 오래걸리는 심사관에게 모두가 검사를 받는 경우

 

그 후 이분 탐색을 시작합니다.

 

mid 는 이름 그대로 중간값입니다.

 

우리는 이제 이 중간값을 기준으로 탐색 범위를 줄여거는 겁니다.

 

total 은 특정 시간에 n명을 다 심사할 수 있는 지를 파악하는 데 사용합니다.

 

total 이 n보다 크다면 이 시간 안에 심사가 가능하다는 의미이고,

 

작다면 시간이 부족하다는 겁니다.

 

 

 

 

다음에 또 봐요