18. 입국심사 ★★

유형 : 이분 탐색

풀이 시간 : 인터넷 검색 

 

def solution(n, times):
    times.sort()
    answer = 0
    #이분 탐색
    start = 0
    end = n * times[len(times)-1] #최댓값 = 가장 오래 걸릴 경우 
    
    while start <= end:
        # 가운데 지점 지정 
        mid = (start + end) // 2
        
        # mid 시간에 처리할 수 있는 사람 수 구하기 
        people = 0
        for t in times:
            people += (mid // t) 
            
        # 이분 탐색 
        if people < n: #탐색 불가능한 경우
            start = mid + 1 # 답은 뒤쪽에 있으므로 뒤를 탐색 
        elif people >= n: #탐색 가능한 경우
            answer = mid #우선 답을 저장 
            end = mid - 1 #더 작은 값을 찾기 위해 앞부분 탐색 
            
    return answer

 

풀이법이 정말 기발한.. 문제였다.

이게 왜 이분탐색이야!? 싶었던 문제...

 

0~최대 시간까지의 범위에서

mid 시간을 지정, 그 시간 내에 검사할 수 있는 사람의 수를 구하고

검사 가능한 사람의 수가 목표보다 더 많다면 (성공) = 저장 후 탐색 계속 (앞부분)

검사 가능한 사람의 수가 목표보다 더 작다면 (실패) = 뒷부분 탐색!