[백준] 1561번 놀이 공원 - Python / 알고리즘 중급 1/3 - 이분 탐색 (연습)

ByungJik_Oh·2025년 7월 15일

[Baekjoon Online Judge]

목록 보기

199/244

💡 문제

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

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

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

입력

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

출력

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

💭 접근

이 문제를 해결하기 위해선 우선 이분 탐색을 사용하여 입력으로 주어진 n명의 아이들이 모두 놀이기구를 탈 수 있는 최소한의 시간을 구하고, 이때 몇명의 아이들이 탈 수 있는지 구해야한다.
예제를 통해 알아보자.

예제 3
n = 22, m = 5
time = [1, 2, 3, 4, 5]

우선 아이들이 시간대별로 어떤 놀이기구를 타게 되는지 살펴보자.

위 그림은 시간(파란색 열)에 따른 아이들의 놀이기구(빨간색 행) 탑승 순서이다.

위에서 볼 수 있듯이 22번째 아이는 9분대에 4번 놀이기구를 타는 것을 알 수 있고, 만약 24번째 아이가 있다면 10분대에 2번 놀이기구를 타게 된다는 것을 알 수있다.

위 그림을 참고해서 이제 문제를 다음과 같은 순서로 문제를 해결해보자.

이분탐색을 활용하여 n명의 아이들이 모두 놀이기구를 타게되는 시간대와 그때 최대 몇명의 아이들이 탈 수 있는지를 구한다.

그렇다면 각 시간대마다 몇명의 아이들이 타는지 어떻게 알 수 있을까?
이는 다음과 같이 구현할 수 있다.
```
cnt = 0
for t in time:
    cnt += mid//t + 1 if mid % t != 0 else mid//t
```
예를 들어 7분대까지 몇 명의 아이가 타게되는지 구해보자.
1번 놀이기구 (운행시간 ⇒ 1분) 7 % 1 = 0 이므로 +7 7 // 1
2번 놀이기구 (운행시간 ⇒ 2분) 7 % 2 ≠ 0 이므로 +4 7 // 2 + 1
3번 놀이기구 (운행시간 ⇒ 3분) 7 % 3 ≠ 0 이므로 +3 7 // 3 + 1
4번 놀이기구 (운행시간 ⇒ 4분) 7 % 4 ≠ 0 이므로 +2 7 // 4 + 1
5번 놀이기구 (운행시간 ⇒ 5분) 7 % 5 ≠ 0 이므로 +2 7 // 5 + 1

따라서 7분대에는 최대 18명의 아이들이 탈 수 있다는 것을 알 수 있다.
1번 단계에서 구한 시간대와 이때 최대 탑승가능한 아이들의 수로 n번째 아이가 몇번째 놀이기구에 타게 되는지 구한다.

위 예시에서 7분대에는 총 18명의 아이들이 탈 수 있다는 것을 알았다.
그렇다면 16번째 아이는 몇번째 놀이기구에 탈 수 있을까?

처음 보았던 그림을 다시 보면 7분대에는 16번째 ~ 18번째 아이가 탈 수 있는 것을 알 수 있다.
따라서 7분대에 탑승 가능한 놀이기구를 거꾸로 탐색하며 16번째 아이가 타게되는 놀이기구를 구하면 된다.
```
# 마지막 아이가 탈 놀이기구 탐색
for i in range(m - 1, -1, -1):
   if time[i] == 1 or last_time % time[i] == 1:
       if last_cnt == n:
           print(i + 1)
           break
       else:
           last_cnt -= 1
```
이처럼 1번 단계에서 16번째 아이도 7분대에 놀이기구를 탄다는 것을 구했으니 7분대에 탑승 가능한 놀이기구를 거꾸로 탐색하며 16번째 아이는 1번 놀이기구를 탄다는 것을 구할 수 있다.

📒 코드

def binary_search():
    start = 1
    end = 6e10

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

        cnt = 0
        for t in time:
            cnt += mid // t + 1 if mid % t != 0 else mid // t

        if cnt >= n:
            res_time = mid
            res_cnt = cnt
            end = mid - 1
        else:
            start = mid + 1
    return res_time, res_cnt
        
n, m = map(int, input().split())
time = list(map(int, input().split()))

if n <= m:
    print(n)
else:
    last_time, last_cnt = binary_search()

    for i in range(m - 1, -1, -1):
        if time[i] == 1 or last_time % time[i] == 1:
            if last_cnt == n:
                print(i + 1)
                break
            else:
                last_cnt -= 1