Level 3

문제

해당 문제 링크

정답

def solution(n, times):
    answer = 0
    # right는 가장 비효율적으로 심사했을 때 걸리는 시간
    # 가장 긴 심사시간이 소요되는 심사관에게 n 명 모두 심사받는 경우이다.
    left = min(times)
    right = max(times)*n
    while left <= right:
        mid = (left+ right) // 2
        people = 0
        for time in times:
            # people 은 모든 심사관들이 mid분 동안 심사한 사람의 수
            people += mid // time
            # 모든 심사관을 거치지 않아도 mid분 동안 n명 이상의 심사를 할 수 있다면 반복문을 나간다.
            if people >= n:
                break
        
        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 많거나 같은 경우
        if people >= n:
            answer = mid
            right = mid - 1
        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 적은 경우
        elif people < n:
            left = mid + 1
            
    return answer

풀이

가장 최악의 경우로 모두 심사하여 걸리는 수를 right으로 한다. 즉 60분이다
입출력 예로 보면, 7분 10분 심사하는 심사위원이 있는데, 10분 심사위원이 n의 값인 6명을 모두 본다고 가정하여 max(times)n = 106 = 60분 걸린다고 가정한다.
최소한의 시간으로 6명의 심사가 끝나야 하는 문제이기 때문에
단순히 3명 3명 나눠 30분 걸리는 것보다 7분 걸리는 심사위원에 4명 10분걸리는 심사위원에 2명을 보내 28분 만에 다 심사를 통과할 수 있는 것이 답이다.

7분 심사위원에게 1명이 심사를 받는 수를 left로 한다. 즉 7분이다.
몇 분 동안 몇 명이 심사를 받을 수 있는지 확인하며 시간을 이진탐색한다.
시간의 최소 범위는 7이다. 7분 심사위원에게 1명이 심사 받는 경우이기 때문이다.

시간의 최소(7), 최대(60) 범위를 구하고 중간 값이 n명을 심사할 수 있는 시간인지 확인하며 이분탐색을 진행한다.
mid로 현재 탐색하는 시간동안 몇 명을 심사할 수 있는지를 알아보자

n명보다 많이 심사 가능하면 => 중간값 기준으로 왼쪽 범위를 탐색하고
n명보다 적게 심사 가능하면 => 중간값 기준으로 오른쪽 범위를 탐색한다.

임의의 시간동안 몇 명을 심사할 수 있는지 확인할 수 있는 방법 (식)
임의의 시간 동안 심사 가능한 사람 수 = (임의의 시간/각 심사관들이 심사하는데 걸리는 시간)
ex) mid=30
(30/7) + (30/10) = 4+3 =7명 심사 가능 n=6보다 더 많이 심사가 가능하기 때문에 중간값 기준으로 왼쪽 범위를 탐색!

참고 코드 및 설명 사이트

이분탐색 문제라길래 풀고자 하는데 왜 이 문제가 이분탐색인지 모르겠어서 ㅠㅠ 그거에 대해 생각해보았다.
이분탐색 알고리즘은 이해했고, 이를 코드로 작성하는 것은 어렵지 않은데
문제마다 보면 이런 알고리즘을 이용하면 되겠지라는 감을 잡아야 할 필요성을 느꼈다..