[Python] 프로그래머스 Lv 3 - 입국심사

이진탐색을 어떻게 써먹는지 알 수 있는 문제

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

알고리즘

그냥 배수를 저장한다던가, 하는 방식으로는 도저히 무리거니와, 입국심사대가 늘어날수록 2개의 쌍만 최소공배수인 경우도 발생하고... 너무 복잡하다. 되도 않는 소리다. 따라서, 방법을 바꿔야 한다.

시간을 많이 줄수록 입국심사대에서 처리할 수 있는 사람은 많을거니까, 아예 시간을 기준으로 입국심사대가 제한된 인원보다 많거나 같게 처리하면 시간을 줄이고, 덜 통과시키면 늘려버리면 된다. 최소의 지점이 바로 최소시간이 될 것이고 이는 이진탐색으로 구현 가능하다.

right의 지정이 문제인데, 최소 개수의 *  n만큼만 하면 충분하다.

그거보다 다른 입국심사대가 늦는다면 제일 최소애가 일을 몰빵받아서 처리하면 그만이고, 아닐 경우 최소에서 일부의 개수는 나머지가 처리해줄 것이기에, 최소시간 * 인원수 만큼만 최대 제한시간으로 처리하면 그만이다.

코드

def solution(n, times):
    left = 0
    right = min(times) * n
    answer = right
    
    while left <= right:
        task_time = 0
        mid = (left + right) // 2
        
        for time in times:
            task_time += mid // time
        
        if task_time < n:
            left = mid + 1
            
        else:
            right = mid - 1
            if mid < answer:
                answer = mid
    return answer