백준 온라인 저지, 이진탐색 / 1561번: 놀이공원 (파이썬 / 백준 골드문제)

문제

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

문제 정의

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.
모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.
놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

3 5
7 8 9 7 8

예제 출력 1

3

접근 방법

- 주어진 m의 최소 공배수를 구한 뒤, 이를 각 m으로 나눈 값의 합(cycle)을 n에다가 나누어 나머지를 n에다 저장한다.
- 이후 start에 0, end에 cycle을 저장한 뒤, n보다 크거나 같은 인원수가 놀이기구에 탑승할 수 있는 최소 시간(time)을 구한다.
- time - 1을 했을 때의 인원수를 구한 뒤, 놀이기구를 하나씩 탐색하며 인원수가 n이 되는 순간을 구해 해당 놀이기구의 인덱스를 출력한다.

코드

# https://www.acmicpc.net/problem/1561
# 접근 방법 (최소 공배수를 구하는 과정이 없이 바로 이진탐색을 진행할 수 있지만 c언어의 최대 정수 크기를 고려해볼 때 문제에서 요구하는 문제 상황과는 다르다고 판단해 이를 나눠준 뒤, 문제를 해결하고자 했다.)
# 주어진 m의 최소 공배수를 구한 뒤, 이를 각 m으로 나눈 값의 합(cycle)을 n에다가 나누어 나머지를 n에다 저장한다.
# 이후 start에 0, end에 cycle을 저장한 뒤, n보다 크거나 같은 인원수가 놀이기구에 탑승할 수 있는 최소 시간(time)을 구한다.
# time - 1을 했을 때의 인원수를 구한 뒤, 놀이기구를 하나씩 탐색하며 인원수가 n이 되는 순간을 구해 해당 놀이기구의 인덱스를 출력한다.
import heapq

def GCD(a, b):
    if a % b == 0:
        return b
    return GCD(b, a%b)

def LCM(a, b):
    return a * b // GCD(a, b)

n, m = map(int, input().split())
array = list(map(int, input().split()))

h = []
for x in array:
    heapq.heappush(h, x)
while len(h) != 1:
    x1 = heapq.heappop(h)
    x2 = heapq.heappop(h)
    heapq.heappush(h, LCM(x2, x1))

gcd = h[0]

cycle = sum([gcd // x for x in array])

n %= cycle
if n == 0:
    print(m)
else:
    start = 0
    end = cycle
    time = cycle
    count = cycle

    while start <= end:
        mid = (start+end) // 2
        total = 0

        for x in array:
            total += (mid // x) + 1

        if total >= n:
            time = min(mid, time)
            count = min(count, total)            
            end = mid - 1

        else:
            start = mid + 1
    count = sum([(time - 1) // x + 1 for x in array])
    for i in range(m):
        if time % array[i] == 0:
            count += 1
            if count == n:
                print(i+1)