[백준(BOJ)] #1561- 놀이 공원 (파이썬, PyPy3)

문제

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

1561번: 놀이 공원

 

---

문제 풀이

해당 문제는 이분 탐색으로 해결할 수 있습니다.

2022.08.11 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search)

[파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search)

 

문제에서 주어진 예제 입력 3을 사용하여 N명의 아이들이 어떻게 놀이 기구에 탑승하는지 확인해보겠습니다.

 

0분 - 5명의 아이들이 순서대로 놀이 기구에 탑승

 

1분 - 1번 놀이 기구의 운행 시간이 끝나 6번째 아이가 1번 놀이 기구에 탑승

 

2분 - 1번 놀이 기구와 2번 놀이 기구의 운행 시간이 끝나 7, 8번째 아이들이 각각 1, 2번 놀이 기구에 탑승

 

3분 - 1번 놀이 기구와 3번 놀이 기구의 운행 시간이 끝나 9, 10번째 아이들이 각각 1, 3번 놀이 기구에 탑승

 

4분 - 1번 놀이 기구와 2번 놀이 기구 그리고 4번 놀이 기구의 운행 시간이 끝나 11, 12, 13번째 아이들이 각각 1, 2, 4번 놀이 기구에 탑승

 

5분 - 1번 놀이 기구와 5번 놀이 기구의 운행 시간이 끝나 14, 15번 째 아이들이 각각 1, 5번 놀이 기구에 탑승

 

6분 - 1번 놀이 기구와 2번 놀이 기구 그리고 3번 놀이 기구의 운행 시간이 끝나 16, 17, 18번째 아이들이 각각 1, 2, 3번 놀이 기구에 탑승

 

7분 - 1번 놀이 기구의 운행 시간이 끝나 19번 째 아이가 1번 놀이 기구에 탑승

 

8분 - 1번 놀이 기구와 2번 놀이 기구 그리고 4번 놀이 기구의 운행 시간이 끝나 20, 21, 22번째 아이들이 각각 1, 2, 4번 놀이 기구에 탑승

 

이렇게 22명의 아이들이 8분에 놀이 기구를 탑승합니다.

 

여기서 시간 T에 놀이 기구 R(운행 시간)에 탑승한 아이들의 수 N일 때

N = T / R (T >= 1)

라는 공식을 얻을 수 있습니다.

(T = 0일 때 즉, 0분 일 때는 놀이 기구의 개수만큼 아이들이 탑승)

 

8분이라는 시간에서 1번 놀이 기구에 탑승한 아이들의 수는 8 / 1 = 8명

8분이라는 시간에서 2번 놀이 기구에 탑승한 아이들의 수는 8 / 2 = 4명

8분이라는 시간에서 3번 놀이 기구에 탑승한 아이들의 수는 8 / 3 = 2명

8분이라는 시간에서 4번 놀이 기구에 탑승한 아이들의 수는 8 / 4 = 2명

8분이라는 시간에서 5번 놀이 기구에 탑승한 아이들의 수는 8 / 5 = 1명

 

시간의 범위를 이분 탐색으로 모든 아이들이 놀이 기구에 탑승할 수 있는 최소 시간을 구하면 마지막 아이가 탑승한 시간을 알 수 있습니다.

 

그럼 마지막 아이가 탄 놀이 기구의 번호는 어떻게 구할 수 있을까요?

 

먼저 위에서 구한 최소 시간 T에서 바로 이전 시간 T-1에 탑승한 아이들의 수 TN을 구합니다.

T % R(놀이 기구)이 0이 되는 R이 T에서 탑승할 수 있는 놀이 기구를 의미합니다. 따라서 T에 모든 놀이 기구를 차례로 순회하면서 탑승할 수 있는 놀이 기구에 남은 아이들을 태우면서 TN을 1씩 증가시킵니다.

TN이 N이 되면 즉, 마지막 N번 째 아이가 놀이 기구에 탑승하면 해당 놀이 기구의 번호를 구해주면 됩니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

# 특정 시간 안에 놀이 기구를 탄 아이들의 수를 반환
def get_rider_cnt(M, a, time):
    # 0분에서는 모든 놀이기구를 탑승하기 때문에 sum_p의 기본값은 M
    sum_p = M
    for c in a:
        sum_p += time // c
    return sum_p

# 모든 아이들이 놀이 기구를 탄 시간을 이분 탐색을 사용하여 반환
def get_time(N, M, a, MAX_PT):
    time = 0
    lt = 0
    rt = N // M * MAX_PT

    while lt <= rt:
        mid = (lt + rt) // 2
        sum_p = get_rider_cnt(M, a, mid)
        if sum_p >= N:
            rt = mid - 1
            time = mid
        else:
            lt = mid + 1

    return time

# 마지막 아이가 탑승한 놀이 기구의 번호반환
def get_last_ride(N, M, a, time):
    rider_cnt = get_rider_cnt(M, a, time - 1)
    for i in range(M):
        if time % a[i] == 0:
            rider_cnt += 1
        if rider_cnt == N:
            return i+1


if __name__ == "__main__":
    MAX_PT = 30
    N, M = map(int, input().split())
    a = list(map(int, input().split()))

    time = get_time(N, M, a, MAX_PT)
    # 0분에 모든 아이들이 탑승 가능하면 N번 놀이 기구가 마지막 번호가 됨
    if time == 0:
        print(N)
    else:
        print(get_last_ride(N, M, a, time))

결과