문제
접근
이 문제도 이분탐색 문제이다.
제한 사항을 보면 범위가 매우 큰 걸 볼 수 있는데, 이런 경우 일반적으로 완전탐색처럼 전체를 본다는 생각을 버려야 한다.
이 경우에는 특정 시간이 t가 있을 때, 해당 시간에 모든 심사자가 심사를 받을 수 있는지 판단할 수 있으면 된다.
그럼 모두 심사를 받을 수 있는 t 중에 최소값을 찾으면 된다.
이 때 t를 이분탐색으로 줄여나간다면 쉽게 정답을 찾을 수 있다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(n, times):
start = 1
end = n * min(times)
answer = end
while start <= end:
mid = (start + end) // 2
now_n = n
for time in times:
now_n -= (mid // time)
if now_n > 0:
start = mid + 1
else:
if answer > mid:
answer = mid
end = mid - 1
return answer