이분탐색 - 입국심사

문제 설명

프로그래머스

 

나의 풀이

# 2*7=14, 4*10=40 -> 40
# 3*7=21, 3*10=30 -> 30
# 4*7=28, 2*10=20 -> 28
# 5*7=35, 1*10=10 -> 35
# x0*times[0], x1*times[1], ... xn*times[n] -> 값들 중 최대가 되는 값, x0+x1+...xn = n

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

 

left = 최소, right = 최대 -> 답이 될 수 있는 값을 이분탐색을 통해 추론해 나가는 문제이다. 처음 left, right는 해당 결과값에서 나올 수 있는 최소와 최대로 두고 mid = left + right //2 중간값을 통해 값을 추적해 나간다.

mid를 times로 나눈 몫들의 합은 n 즉, 사람들의 수와 같아야한다. 만약 n보다 나눈 몫들의 합이 크다면 우리가 추적해가는 목표값보다 mid가 더 크기 떄문에 left를 mid + 1로 재설정해준다. 그리고 더 작다면 right = mid -1 로 재설정한다.

이러한 과정을 반복하여 left, right, mid가 모두 같아지는 시점이 우리가 찾는 목표값이 된다.

 

 해당 문제는 코드를 짜는 것보단 이분 탐색을 어떻게 문제에 적용하여 풀지가 핵심인데, n에 초점을 두고 문제를 풀면 잘 풀리지 않는다. times를 기준으로해서 알고리즘을 생각해본다면 접근이 쉬워진다.