알고리즘
자료구조
[1561] 놀이 공원
by Hwang
문제
https://www.acmicpc.net/problem/1561
풀이
처음 M명은 차례대로 놀이기구를 타면 되기 때문에 N이 M보다 작거나 같다면 N을 그대로 출력해줍니다.
만약 N이 M보다 클 경우 이분 탐색을 이용해서 모든 아이를 태울 수 있는 시간을 구해주면 됩니다.
가능한 모든 범위에서 이분 탐색을 해주며 모든 아이를 태울 수 있는 가장 작은 수를 구했다면 (태워야하는 사람의 수 - (구한 시간-1)) 을 해줘서 마지막 시간에 남은 사람의 수를 구할 수 있고, 마지막 인원이 무슨 놀이 기구를 타는지 구할 수 있습니다.
import sys
N, M = map(int, sys.stdin.readline().split())
times = list(map(int, sys.stdin.readline().strip().split()))
# 처음 M명은 차례대로 놀이기구를 타면 되기 때문에 N이 M보다 작거나 같다면 N을 그대로 출력
if N <= M:
print(N)
exit()
# 현재 시간까지 놀이 기구를 태울 수 있는 총 인원을 반환
def get_played(current_time):
count = 0
for time in times:
count += current_time // time
return count
left, right = 0, max(times) * N
result_time = 0
target = N - M # 처음 M명은 차례대로 놀이기구를 태웠기 때문에 N - M
while left <= right:
mid = (left + right) // 2
total = get_played(mid)
if total >= target:
right = mid - 1
result_time = mid
else:
left = mid + 1
remain = target - get_played(result_time - 1)
for i, time in enumerate(times):
if result_time % time == 0:
remain -= 1
if remain == 0:
print(i + 1)
break
Comment