프로그래머스 입국심사 with Python

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

프로그래머스

 

def solution(n, times):
    answer = 0
    
    # 최대 시간
    max_times = n * max(times)
    
    s, e, m = 1, max_times, 0
    
    while s <= e:
        m = (s+e)//2
        
        # 심사 가능 명수
        cnt = 0
        
        for t in times:
            cnt += m//t
            
        if cnt < n:
            s = m + 1
        else:
            answer = m
            e = m - 1
            
    return answer

 

이 문제를 처음보고 했던 생각은 심사위원 한명한명 로테이션을 돌리는 방법이 아닌 뭔가 다른 방법이 있을 것 같다 라고 생각했다.

일단 최대로 걸릴 것 같은 시간을 구한뒤 (기다리는 사람 * 제일 긴 심사 시간) 그 시간을 좁혀보자가 아이디어였다.

 

예를 들어 30분이 정답이라고 놓고 보면

7분 심사위원은 4명을, 10분 심사위원은 3명을 심사할 것이다. (비동기로 진행하기 때문에)

그럼 총 30분이면 7명을 심사할 수 있는 것이다.

 

이러한 느낌으로 이분탐색을 사용하여 최적의 시간을 찾아갔다.

여기서 가장 중요한 포인트는 어 6명 심사 가능이네? 정답이다! 가 아닌

6명 가능이지만 가능한 시간중에서도 가장 짧은 시간을 구해야한다는 것이다.

그래서 6명이 가능일 때도 일단 answer에 저장을 하고 계속 해서 이분탐색을 이어나가고 s가 e를 이기는 순간이 오면 종료한다.

이 때 저장된 값이 가장 짧은 시간일 것이다!