[이진탐색] programmers 입국 심사 문제 풀이

입국심사를 받아야 하는 n명의 사람이 있을 때 심사관들은 심사할 때 각각 주어진 times와 같은 시간이 소요된다. 

총 n명의 사람이 전부 검사를 받는데 걸리는 최소의 시간을 구하는 문제였다. 

일단 n명의 사람이 검사받는데 걸리는 최악의 시간은 가장 오래 시간이 소요되는 심사관에게 모든사람이 검사를 받는 경우이다. 

이진 탐색을 이용해 left = 0 right= 최악의 시간으로 하여 가장 최소로 걸리는 시간을 찾는다. 

left = 0
    right = max(time_list) * n  # 모든사람이 다 받을 때 끝나는 시간의 최악의 경우

    while left <= right:
        mid = (left + right) // 2
        people = 0
        for i in time_list:
            # 각 심사관들이 mid 시간안에 검사를 끝낼 수 있나
            people += (mid // i)
        # mid 시간안에 최대로 검사할 수 있는 인원 = people
        if people >= n:
            answer = mid
            right = mid - 1
        elif people < n:
            left = mid + 1
    print(answer)

나는 이진탐색을 구현하면서 각 심사관들이 특정 시간안에 검사를 끝낼 수 있는지 확인하는 조건을 만드는 것이 좀 어려웠다.  일단 time_list를 도는 for문을 만들고 각각의 심사위원들이 주어진 시간안에 최대 몇명의 사람들을 검사할 수 있는지 구하고 그 모든 수를 people에 더한다.

즉 people보다 n이 더 크다면 주어진 시간(mid)안에 심사를 하지 못하는 것이고 n이 더 작다면 주어진 시간안에 심사가 가능한것이다. 

최소시간을 구할 때까지 이 과정을 반복한다.