백준 1561번 문제
해설
이분 탐색을 살짝 응용한 문제다. N이 20억이기 때문에 N을 이용하려면 logN의 속도로 처리해야 하기 때문에, 이분 탐색이 적절할 것이라고 생각하면 될 것 같다.
놀이기구와 타는 애들과의 관계를 표로 잘 정리하면, 특정 시간 n(소스 코드에선 mid가 해당됨)에 애들을 여태까지 몇 명 태웠는지를 계산 할 수 있다. 이 시간을 이분 탐색을 이용해 바꿔가며 여태까지 태운 아이들의 명수와 N이 가장 가까운 시간을 뽑아내서, 정확히 N명을 태웠을 경우 어떤 놀이기구를 타는 지 확인하면 된다.
구현
N, M = map(int, input().split())
t = list(map(int, input().split()))
l = 1
r = 10**20
max_m = max_s = 0
while l <= r:
mid = (l+r)//2
s = sum((mid-1)//x + 1 for x in t)
if s < N:
if max_m < mid:
max_m = mid
max_s = s
l = mid + 1
else:
r = mid - 1
for i, k in enumerate(t):
if max_m % k == 0:
max_s += 1
if max_s == N:
print(i+1)
break