[백준/1561] 놀이 공원 (Python)

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

1561번: 놀이 공원

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:51:20

 

---

 

문제 설명

 

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

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

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

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

3 5
7 8 9 7 8

 

출력 예시

 

3

 

 

---

 

풀이

 

맨 처음에는 최소공배수로 패턴을 찾아 나눠 주고 힙으로 풀이하려고 했다. 당연히 시간초과였다..
가령 M_list가 [2, 4, 3]이고 N = 30이라 하자. 최소공배수는 12이고, 12분이 하나의 주기가 된다. 12분동안 처리할 수 있는 총 사람의 수는 12/2 + 12/4 + 12/3 = 13이다. 즉 N % 13 = 4에 대해서만 힙으로 일일히 계산해주면 된다.

극단적인 예시로, 1~30의 최소공배수는 2,329,089,562,800으로 최대 N범위보다 크다. 즉 이러한 경우에는 모든 경우를 하나씩 따져보며 힙으로 연산하는 것과 다를 바 없으며, O(NlogM)의 시간복잡도로 시간

 

 

두 번째 방법은 이분 탐색을 이용하는 것이다. 본 이분 탐색의 목적은 N명 이상을 처리 가능한 최소 시간 M'을 구하는 것이다. 초기값은 0, N*30으로 둘 수 있는데, 최소 1개의 놀이기구가 운행 시간이 30분인 최악의 경우 필요한 시간이 N*30이기 때문이다.

이 때 mid에 따른 매개변수값은 (mid) // (각 놀이기구의 운행 시간 주기) + 1의 합이 된다. mid 시간 내에 놀이기구에서 탈 수 있는 사람의 수를 의미한다. 이를 lower bound를 가지고 연산하면, 최적의 M'과 이 때의 사람의 수 N'을 구할 수 있다. 이 때 시간복잡도는 O(MlogN)이 된다.

 

여기서 끝이 아니다. 사람의 수 N' >= N이므로, 정확히 몇 번째 놀이기구에서 N번째 사람이 탔는지를 찾아내야 한다. M번째 놀이기구부터 역순으로 찾으며, M' % time[i] == 0인(즉 나누어 떨어지는) 놀이기구를 만날 때마다 N'을 체크한다. 나누어 떨어진다는 뜻은, M'시점에 어떤 사람이 그 놀이기구를 이용할 가능성이 있기 때문이다. 만약 N' == N이면 그 놀이기구가 정답이 되며, 그렇지 않다면 그 앞의 놀이기구가 정답 후보가 되므로 N'에서 1을 제거한다.

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
play_time = list(map(int, input().split()))

start, end = 0, N*30
val = float('inf')
while start < end :
  mid = (start + end) // 2
  tmp = 0
  for t in play_time :
    tmp += mid // t + 1
  if tmp < N :
    start = mid + 1
  else :
    end = mid
    val = min(val, tmp)

for i in range(M-1, -1, -1) :
  if end % play_time[i] == 0 :
    if val == N :
      print(i+1)
      break
    val -= 1

풀이 완료!