문제
접근
이분 탐색 문제이다.
시간을 변수로 해서 이분탐색을 진행하면된다.
최소는 1이고, 최대는 가장 시간이 긴 놀이기구에 n명이 모두 탔을 때다.
이분 탐색을 진행하며 해당 시간이 지났을 때 탑승한 인원이 n보다 크다면 정답 후보가 된다.
정답 후보들 중 최소값이 n명을 모두 탑승시킬 수 있는 최소 시간이 된다.
문제는 n번째 아이가 탑승할 놀이기구를 찾아야한다.
따라서 n명이 모두 탈 수 있는 시간을 t라고 하면 우리는 t-1시간이 필요하다.
t-1시간에서 놀이기구를 아직 타지 못한 인원과 현재 놀이기구의 상태(탑승가능한 상태가 되려면 몇 초 남았는지)를 안다면
n번째 아이가 어떤 놀이기구에 탑승할지 알 수 있다.
t-1 시간에서 (탑승 가능한 상태까지 남은 시간, 놀이기구 번호)로 배열을 만들어주고, 정렬해주면 손쉽게 구할 수 있다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys
input = sys.stdin.readline
def binarySearch(start, end, arr, n):
ans = float('inf')
while start <= end:
mid = (start+end)//2
if isPossible(mid, arr, n):
end = mid - 1
ans = min(ans, mid)
else:
start = mid + 1
return ans-1
def isPossible(mid, arr, n):
ans = 0
for item in arr:
ans += (mid // item) + (1 if mid % item > 0 else 0)
if ans >= n:
return True
else:
return False
if __name__ == "__main__":
n, m = map(int, input().split())
arr = list(map(int, input().split()))
start = 1
end = max(arr) * (n)
times = binarySearch(start, end, arr, n)
ans = 0
rem_arr = []
for idx, item in enumerate(arr):
rem = times % item
ans += (times // item) + (1 if rem else 0)
rem_arr.append((rem, idx))
rem_arr = sorted(rem_arr, key = lambda x:(x[0], x[1]))
print(rem_arr[n-ans-1][1]+1)