[Python][프로그래머스][Level3] 입국심사

[Python][프로그래머스][Level3] 입국심사

코드

def solution(n, times):
    start, end = 0, min(times)*n
    
    while start<=end:
        middle = (start+end)//2
        check=sum([middle//time for time in times])
        if check>=n:
            end=middle-1
        else:
            start=middle+1
    return start

이분탐색으로 풀었다.

이렇게 다짜고짜 범위가 굉장히 넓은 문제는 이분탐색인 경우가 많은것 같다.

정답의 최소는 0이고 최대는 times에서 가장 적게 걸리는 검색대에서만 심사를 전부 실시하는 경우(min(times)*n)이다.

그리고나서 middle인 시간일 때, 심사를 끝내는 명 수가 n보다 크거나 같으면 end=middle-1이 되고

작으면 start=middle+1이다.

이렇게 진행하다보면 end가 n과 같았다가 middle-1이 되었을 때 n-1인 경우가 생긴다.

그러면 end는 계속 고정되고 start만 계속 늘어나다가

end+1이 되고 그 값이 정답이 된다.