[Python 3] BOJ - 1561 "놀이 공원"

 # 문제 링크 : https://www.acmicpc.net/problem/1561

1561번: 놀이 공원

 # 풀이 :

개인적으로 이 문제는 이분탐색이 핵심이라 생각한다. 실제로 최대 입력인 20억일 때 선형으로 탐색하게 되면 시간 초과를 피할 수 없기 때문이다. 따라서 k분일 때 1분부터 k분까지 총 놀이기구를 이용한 어린이 수를 계산할 수 있으면 이분 탐색을 이용해 정확히 끝나는 시간을 알 수 있다.

<그림 1. 4초까지의 경우>

 5개의 놀이기구가 각각 1분, 2분, 3분, 4분, 5분의 운행시간을 가지는 경우를 각 분에 따라 탈 수 있는지 없는지를 나타내는 경우를 그림 1로 나타내었다. 따라서 k분인 경우 탈 수 있는 놀이기구는 운행 시간이 k분의 약수인 놀이기구이다. 따라서 i번째 놀이기구에서 0분부터 k분까지 놀이기구를 이용한 사람의 수는 k / i번째 놀이기구의 운행시간이다.

 위의 그림 1에서 8분까지 운행하면 22명의 모든 사람이 놀이기구를 이용하게 된다. 그런데 위의 그림을 통해 8초의 경우 8의 약수인 운행 시간을 갖는 인덱스 0, 인덱스 1, 인덱스 3의 놀이기구이다. 바꿔 말해, 8초가 되는 순간 3개의 놀이기구가 비게 되는데 문제에서 여러 개의 놀이기구가 있다면 작은 번호 순으로 타므로 가장 마지막 사람은 가장 마지막 인덱스의 놀이기구를 타게 된다.

 따라서, 만일 k분에 모든 사람이 탄다면 전체 사람의 수 n에서 k - 1분까지 탄 사람의 수를 빼면 k분일 때 타는 사람의 수를 구할 수 있으므로 놀이기구 배열을 순회하면서 k의 약수인 수의 인덱스 중 n번째를 고르면 정답을 구할 수 있다.

 

 # 코드

import sys

# times : 배열 a가 주어질 때 0부터 t분까지 처리한 사람의 수를 리턴하는 함수
def times(a,t):
    cnt = 0
    for i in a:
        cnt += t // i
    return cnt

# go : 이분 탐색을 통해 정확히 주어진 n명의 사람만 처리하는 시간을 ans에 갱신하는 함수 
def go(left, right):
    global ans
    while left <= right:
        mid = (left + right) // 2
        res = times(amuse, mid)
        if res >= n - m:
            right = mid - 1
            ans = mid
        else:
            left = mid + 1

# adjust : a분일 때 남는 놀이기구 중 n번째 인덱스를 리턴하는 함수
def adjust(a, n):
    th = []
    for idx, i in enumerate(amuse):
        if a % i == 0:
            th.append(idx)
    return th[n - 1] + 1

# 입력부
n,m = map(int, sys.stdin.readline().split())
amuse = list(map(int, sys.stdin.readline().split()))

# 놀이기구 수가 사람 수 보다 많으면 0분에 모든 사람이 탈 수 있다
# 그런데 작은 번호부터 먼저 타므로 n번째 놀이기구에 n번째 사람이 타게된다
if n <= m:
    print(n)
else:
    ans = 0
    # ans 갱신
    # 여기서 left를 1, right를 문제의 최대 입력으로 하지 않은 이유는 실제 끝나는 시점이
    # 문제의 최대 입력(20억)보다 클 때가 존재하기 때문이다
    go(min(amuse), max(amuse) * n)
    # k : 정확히 끝나는 ans시점에 탈 사람의 수
    k = n - m - times(amuse, ans - 1)
    # 정답 출력
    print(adjust(ans, k))