[이분탐색] 입국심사 (파이썬)

문제 설명

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

프로그래머스

문제 풀이

• 시간부터 사람까지 값의 범위가 10억으로 굉장히 광범위함.
• 걸리는 시간의 최솟값을 구하는 것이므로 특정 시간대에서의 행할 수 총 사람 수를 구해본다.
• 사람 수가 n 이상이라면 해당 시간대에서는 모두 처리 할 수 있다는 것이므로 시간의 줄여본다.(end를 mid-1 로)
• 사람 수가 n 미만이라면 해당 시간대에서는 처리 불가이므로 시간대를 늘려봄(start를 mid+1로)

소스 코드

def solution(n, times):
    answer = 0
    end = n*max(times)
    start = 0
    while(start<=end):
        mid = (start+end)//2
        s=0
        for t in times:
            s+=mid//t
            if s>=n:	#만약 n이상이라면 이 시간대는 가능하다는 것이므로 break 걸고 다음 시간대 찾아본다
            	break
        if s>=n:
            end = mid-1
        else:
            start=mid+1

    return start

print(solution(6,[7, 10]))