[Python/파이썬] 백준 1561번 놀이 공원

1561번: 놀이 공원

 

문제

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
times = list(map(int, input().split()))
if n < m:
    print(n)
else:
    s, e = 0, sys.maxsize
    minute = 0  # 원하는 명수를 태운 시점
    while s <= e:
        mid = (s+e)//2
        total = m
        for t in times:
            total += (mid//t)
        if total >= n:
            e = mid-1
            minute = mid
        else:
            s = mid+1
    cnt = m
    # 원하는 명수를 태우기 1분 전 탄 사람들의 수 총합
    for t in times:
        cnt += (minute-1)//t
    # 원하는 명수를 태운 시점에 탈 수 있었던 놀이기구 파악
    for i in range(len(times)):
        if (minute % times[i]) == 0:
            cnt += 1
        if cnt == n:
            print(i+1)
            break

 

n의 범위가 너무 커서 보자마자 이분탐색을 이용해야겠다는 생각을 했다.

이분탐색, 정확히 말하자면 매개 변수 탐색을 이용하여 우리가 원하는 인원수를 모두 태운 시점을 구한다. 몇분까지 몇명이 탔는지는 구하려는 시간에 각 놀이기구의 탑승시간을 나눈 몫들의 합을 구해보면 된다. n명 이상을 태운 최소 시점을 구하면 된다.

최소 시점을 구한 뒤에는 몇 번 놀이기구에 n번이 탔는지 구하면 된다. 구한 최소 시점에 탈 수 있는 놀이기구는 최소 시점과 각 놀이기구의 탑승시간을 나눈 나머지가 0인 놀이이구들이다.