[백준] 놀이공원

https://www.acmicpc.net/problem/1561

1561번: 놀이 공원

이분탐색

import sys

def solution(n,m,time):
    
    def get_prev_time_list(time,mid):
        prev_time = mid - 1
        total = m
        for t in time:
            total += prev_time // t
        return total
    
    left = min(time)
    right = max(time) * n
    ans = right
    mid = right
    
    if n <=m:
        return n
    
    while left<=right:
        total = m
        mid = (left+right) // 2

        for t in time:
            total += mid//t
            if total >= n:
                right = mid - 1
                ans = mid
                break
        else:
            if total < n:
                left = mid +1
            
    prev_total= get_prev_time_list(time, ans)
    # print(prev_total)
    answer = 0
    for idx in range(m):
        if ans % time[idx] == 0:
            prev_total += 1
            if prev_total == n:
                answer = idx+1
                break 
    return answer

n,m = map(int, sys.stdin.readline().split())
time = [*map(int, sys.stdin.readline().split())]

print(solution(n,m,time))