백준 1561번(파이썬):놀이공원
백준 1561번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/1561
문제 내용
나의 풀이
n, m = map(int,input().split())
play=list(map(int,input().split()))
if n<=m:
print(n)
else:
res=0
start,end=0,60000000000
while start <= end:
mid = (start + end) // 2
temp=m
count=0
count_index=[]
for i in range(m):
temp += mid//play[i]
if mid%play[i]==0:
count+=1
count_index.append(i)
if temp >= n: #이분탐색 실행
if temp-(count-1)<=n<=temp:
num=-(temp-n+1)
res=count_index[num]+1
end = mid - 1
else:
start = mid + 1
print(res)
우선 경과된 시간을 이분탐색하여 맨 마지막 사람이 탑승할 놀이기구를 구하려고했다.
(start,end=0,놀이기구 운행시간들의 최소공배수)로 설정n<=m일 때는 그냥 n번째 놀이기구를 탑승한다.
n>m일 때는 mid시간 경과 되었을때, 현재까지 탑승한 인원수는
mid를 각 놀이기구의 운행시간으로 나눈 몫들의 합+m이다.그 후 조건에 맞는 범위에 들어오면 mid시간에 들어간 사람수를 이용하여 마지막 사람이 탑승한 놀이기구를 찾도록 했다.
하지만 시간 초과가 발생했다… 그래서 찾아보니 end값을 나올 수있는 가장 큰 값인 60000000000으로 하니 맞았다…
풀이를 본 후
과정이 완전히 똑같아서 본 결과 end값을 넣을 수있는 최대값을 넣어줘야 한다…
해결한 후
이분탐색에서 가장 큰 값은 문제에서 조건에 따라 최대값을 설정해주면 된다… 아마 최소공배수를 계산하는 부분에서 시간초과가 발생한것 같다…
