[프로그래머스] 알고리즘 고득점 Kit - 이분탐색 입국 심사

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

프로그래머스

def solution(n, times):
    answer = 0
    times.sort() # O(NlogN)
    
    start = 1
    end = times[-1] * n
    
    while start <= end:
        mid = (start + end) // 2
        count = 0
        times.sort() 
        for i in times: 
            count += (mid // i)
        if count >= n: # 더 많은 사람을 받을 수 있음, 시간 줄이자
            result = mid
            end = mid - 1
        else:
            start = mid + 1

    return result

1. 시작 시간은 1분으로 잡고, end는 모든 사람이 가장 오래걸리는 심사위원에게 받는다고 가정

2. N의 범위가 매우 크므로 , O(logN)을 생각할 것, N도 위태롭고 N^2은 빼박 시간초과가 뜰 것

3. count += (mid // i) -> 카운트는 각 심사위원이 심사할 수 있는 사람을 카운트하고,

4. 만약 count >= n (아직 심사위원들이 n보다 더 심사할 수 있거나 같다면 , 시간을 줄일 수 있음)

5. 만약 n 미만이라면 , 시간을 늘려야 하므로 start = mid + 1

 

요약 : 문제 좋은 것 같다.