문제
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.
입출력 예
| n | times | return |
|---|---|---|
| 6 | [7, 10] | 28 |
입출력 예 설명
가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
풀이
답을 answer라고 정해놓았다고 가정을 하자.
그러면 이 시간안에 처리할 수 있는 사람의 수는 다음과 같이 구할 수 있다.
n = answer//times[0] + answer//times[1] + .. + answer//times[-1]즉 심사관 한 명이 시간 안에 처리할 수 있는 사람의 수는 (주어진 시간)/(심사관이 걸리는 시간)의 몫이 될 것이다. 이 사람의 수를 모두 합하면 시간에 처리할 수 있는 사람의 수 합이 된다.
이렇게 구해야할 답이 수식 안에 들어가 있을 때는 이분탐색을 사용한다.
비슷한 예로 백준 2512, 프로그래머스 예산이 있었다.
이분탐색하는 구간
탐색 할 요소는 총 걸리는 시간(찾는 요소)이 된다. 걸릴 수 있는 시간의 범위에서 그 중간 값을 가져온다. 중간값을 이용해 최대 처리할 수 있는 사람 수를 sum으로 구한다. sum이 n보다 작으면 위쪽을 탐색하고, 크면 아래쪽을 탐색하도록 한다.
여기서 주의를 할 점은 합이 n이 되는 시간이 여러개가 될 수 있다는 점이다. 그 중에 최소값을 구해야 한다. 그래서 합이 n보다 작을 때는 무조건 위쪽으로 범위를 옮겨야 하지만 같을 때는 아래쪽을 탐색해도 된다.
while lo <= mx:
mid = (lo + mx)//2
sum = 0
for i in range(len(times)):
sum += mid // times[i]
if sum >= n:
mx = mid - 1
else:
lo = mid + 1최소, 최대 설정
나는 구간을 가장 오래 걸리는 시간과 가장 적게 걸리는 시간을 구해서 만들었다.
최소 시간은 모든 심사대가 times의 min 값을 가진다고 가정하면 총 걸리는 시간은 min * (심사받는사람수)를 심사대 개수로 나눠서 올림을 한다. 최대는 max값으로 한다. 그런데 이 부분도 심사대 갯수가 많으면 꽤 시간이 걸려서 min값은 0으로 할 수도 있다.
최종코드
from math import ceil
def solution (n, times):
answer = 0
lo = ceil(min(times) * n / len(times))
mx = ceil(max(times) * n / len(times))
while lo <= mx:
mid = (lo + mx)//2
sum = 0
for i in range(len(times)):
sum += mid // times[i]
if sum >= n:
mx = mid - 1
else:
lo = mid + 1
return lo여기서 항상 어려웠던 것이 이분탐색하는 구간를 구성하는 요소와 비교할 때 사용하는 값이 다르다는 것이다. 매개변수를 이용하는 것이 이해가 잘 안 됐었다. 그래서 앞의 문제들을 풀 때도 어려웠는데 이번에 이해를 할 수 있게 되었다!
