[이분탐색] 프로그래머스 - 입국심사

링크 - 입국심사

아이디어

문제를 보자마자 공유기 설치 문제 처럼 풀면 되겠다고 생각했다.
만약 count를 mid로 잡아서 문제를 풀게 되면 이분탐색으로 푸는 방법을 떠오르기가 힘들어진다.

mid를 걸리는 시간으로 잡아서 그 시간 내에 입국심사를 하는 사람들의 수를 세어 많다/ 작다를 결정하는 것이 더욱 편리하다.

input
num = 6
times=[7,10]

에서

예를 들어 걸린시간을 30분이라고 둔다면, 30분 동안 병렬적으로 입국심사를 하기 때문에
입국심사를 한 사람은 (30//7)+(30//10) = 4+3 = 7명이 된다.
=> 걸린 시간을 줄여야 한다.

코드

def solution(n, times):
    answer = 0
    times.sort()
    start = times[0] #최소시간
    end = times[-1]*n #최대시간
    while start<=end:
        mid = (start+end)//2
        count=0
        for time in times:
            count+=(mid//time)
        if count>=n: #시간을 더 줄인다
            answer = mid 
            end = mid-1
        else: #시간을 더 늘린다. 
            start = mid+1
    return answer```