입국심사

프로그래머스

심사 받는 데 최소가 되도록 어떻게 이분탐색을 적용하지 고민이 많았는데 모든 문제가 그렇듯 알면 어렵지 않다..

이분탐색을 어떤 원리로 적용하냐면,

1. 전체 걸리는 시간의 최소시간, 최대시간을 설정한다.
   최소시간은 1로 설정했고, 최대시간은 모든 사람이 가장 오래 걸리는 사람에게 심사를 받을 때로 설정한다.
2. 최소와 최대의 중간 값을 구해서 times의 각 시간으로 나누었을 때가 해당 심사관에게 심사받는 사람의 명 수 인데 이 수를 합했을 때 n이상이면 n명을 심사하고 남는 시간인 경우이므로 end를 줄인다.
   n명을 다 심사할 수 없는 시간이라면 start를 키운다.

def solution(n, times):
    times.sort()
    start = 1
    end = times[-1]*n
    
    while start<=end:
        mid = (start+end)//2
        
        cnt = 0
        for t in times:
            cnt += mid//t
            
        if cnt >= n:
            answer = mid
            end = mid-1
        else:
            start = mid+1

    return answer

그리고 잊지 않아야할 것은 이분탐색은 정렬을 먼저 하고 시작해야한다!