[고득점kit]이분탐색 #1. 입국심사
(문제 설명)
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는 데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는 데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
| 6 | [7, 10] | 28 |
가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
(문제 해설)
! 풀기전에 생각해보아요!
심사를 해야하는 사람 6명
심사의원들이 심사 대기 시간 각각 7, 10분
조금만 깊게 생각해보면 10분 걸리는 심사의원한테 6번 받으면 최대 심사 시간이 나온다.
이렇게 심사시간을 계산하는 것부터가 이 문제 풀이의 첫 실마리입니다.
다음으로, 이분탐색이라는 주제에 맞게 0 <- 말이 안되지만 가장 최소로 걸리는 시간, 아까 구한 맥스 시간을
start와 max로 두고 이분탐색을 할 것입니다.
== 문제 풀이 알고리즘 ==
예제 1을 예시로 구현할 알고리즘을 설명합니다.
0. mid = (st + end) // 2 ==> 30 # mid 예상 답 후보가 됩니다.
1. mid만큼 걸린다고 가정합니다.
2. 각각 심사의원들이 mid(30)만큼 심사를 한다고 가정하고 심사를 합니다
2-1. 30 // 7 = 4, 30 // 10 = 3 ==> 총 candi(명): 4 + 3 = 7 명으로 우리가 심사하게 될 n(6) 보다 많이 심사하게 됩니다.
3. 결론적으로, 현재 산정한 mid(분)은 너무 시간이 많은 것
4. end = mid - 1로 줄여서 다시 mid를 계산 ---> 1로 이동
5. 만약, 더한 candi(명)이 심사해야 할 n명보다 작다면 st = mid + 1로 키우는 방식으로 시간을 산정해서 다시 계산합니다 ---> 1로 이동
6. st > end 가회면 해당 알고리즘을 종료 -> mid 답 출력
[ 코드 ]
def solution(n, times):
answer = 0
st = 0
end = max(times) * n
while st <= end:
res= 0
mid = (st + end) // 2
# 중요 부분
for t in times:
res += mid // t
if res >= n:
answer = mid
end = mid - 1
else:
st = mid + 1
return answer후기
이분 탐색을 문제를 정말 빠르고 쉽게 풀 수 있다.
이 문제는 알면 쉽지만 모르면 난감할 수 있습니다