import numpy as np
def solution(n, times):
times = np.array(sorted(times))
min_ = times[0] * (n//len(times))
max_ = times[-1]* (n//len(times))
while min_ < max_ :
estimate = (min_+max_) // 2
total_p = (estimate//times).sum()
if total_p < n :
min_ = estimate+1
else :
max_ = estimate
return int(min_)
이진탐색?
도대체 뭐를 이진탐색 하라는건지 감도못잡는 문제였다. 보통의 알고리즘 문제가 “이러쿵 저러쿵해서 계산해서 이게 답이다!” 하고 푸는 방식이라면 이 문제는 “이게 답일까? 어..아니네? 그럼 이게답인가?” 이런식으로 답을 추정해나가야한다. 그리고 그 답을 찾아나가는 과정이 이진탐색이다.
이 문제에서 추정하고자 하는 값은 바로 심사 시간이다. 시간값을 추정하기전에 추정값 범위를 한번 봅시다.
최소 심사시간 : 제일 빠르게 검사하는 검사관들로만 이루어져있다고 가정
최대 심사시간 : 제일 느리게 검사하는 검사관들로만 이루어져있다고 가정
아니 검사관은 이미 정해져있는데 최소/최대 심사간을 왜 그따구로 정하노ㅡㅡ 하시는 분들이 있을 테지만 최대/최소 추청시간은 깊게 생각할 필요가 없습니다. 최소시간을 1로해도되고 최대시간을 10억을 해도됩니다. 어차피 이진 탐색으로 답을 찾아 나갈꺼기 때문에.
\[검사할수있는인원 = \frac{\widehat{time}}{감독관검사시간}\]
이 공식을 이해해 봅시다. 내가 추정한 시간이 10분이고, 감독관 검사시간이 [3, 7]이 주어졌을 때, 감독관별로 몇명씩 검사 가능할까? [3명, 1명] 검사 가능합니다. 그러면 만약에
야 10분준다, 느그둘이
[3, 7], 7명 검사가능하냐?
둘이 10분동안 최대 4명밖에 검사를 못했네요. 그러면 추정시간을 다시 조정해야하는데 늘려줘야할까요 줄여야할까요?
이정도했으면 이해했다고 봅니다. 이런식으로 추정값을 조정해 나가며, \(\widehat{time}\) 시간이면 n명검사 가능할까? 를 찾아나면 됩니다.
Upper/Lower Bound Binary Search 참고
import numpy as np
def solution(n, times):
times = np.array(sorted(times))
min_ = times[0] * (n//len(times)) # 1해도되고 0해도되고 ㄴ상관
max_ = times[-1]* (n//len(times)) # 10억해도되고 100억해도되고 ㄴ상관
while min_ < max_ : # UpperBound BinarySearch 알고리즘
estimate = (min_+max_) // 2
total_p = (estimate//times).sum() # 총검사 인원 계산
if total_p < n : # 총검사 인원이 n명보다 딸리면
min_ = estimate+1
else :
max_ = estimate
return int(min_)