https://programmers.co.kr/learn/courses/30/lessons/43238
코딩테스트 연습 - 입국심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한
programmers.co.kr
def solution(n, times):
start = 1
end = max(times) * n
while start <= end:
mid = (start + end) // 2
people = 0
for t in times:
people += mid // t
if people >= n:
answer = mid
end = mid - 1
else:
start = mid + 1
return answer탐색 범위가 10억이라서 완전 탐색으로는 풀 수 없다는 것을 알아차려야 한다.
이분탐색으로 풀이하였다.
이분탐색에서 중요한 것은 탐색을 할 대상을 정하는 것과 시작점, 끝점을 정하는 것이다.
이 문제에서는 모든 사람이 심사를 받는데 걸리는 시간을 대상으로 정하였고,
시작점을 최소 시간 1,
끝점을 심사가 가장 오래 걸리는 심사관에게
모든 사람이 심사를 받았을 경우의 끝나는 시간(max(times) * n)으로 하였다.
반복문을 사용한 이분탐색을 하였고 while문에 start <= end 조건을 넣었다.
mid를 계산하여 이 시간동안 심사를 받을 수 있는 사람의 수 people을 계산한다.n보다 크거나 같을 경우 끝점을 end - 1로 조정한다.n보다 작을 경우 시작점을 end + 1로 조정한다.
최종적으로 반복문이 끝나면 이분탐색으로 최적화된 값이 나오게 된다.
