[파이썬/Python] 백준 1561번: 놀이 공원

숨·2025년 1월 13일

코테

알고리즘 문제 풀이

목록 보기

98/105

📌 문제 : 백준 1561번

📌 문제 탐색하기

N : 아이들 수 ( $1 ≤ N ≤ 2,000,000,000$ )
M : 놀이기구 종류 ( $1 ≤ M ≤ 10,000$ )
times: 운행 시간 ( $1 ≤ time ≤ 30$ )

문제 풀이

N명의 아이들이 각각 다른 운행 시간을 가진 M개의 놀이기구를 탄다고 할 때, 마지막 아이가 탈 놀이기구 번호를 출력하는 문제이다.

⭐️ 놀이기구 타는 방법

서 있는 순서대로 놀이기구 탑승

여러 놀이기구 비어있다면 더 적은 번호의 놀이기구부터 탑승

N의 크기가 매우 크기 때문에 순차적으로 찾는 방식으로 푼다면 시간 초과가 발생할 것이다.
→ 시간복잡도를 줄이기 위해 이분탐색 활용한 방법으로 문제를 푼다.

먼저 탐색이 필요한 경우, 필요하지 않은 경우를 각각 고려해준다.

N ≤ M이라면 이분탐색을 하지 않고도 N번 놀이기구라는 것을 바로 구할 수 있다.
그렇지 않다면 이분탐색을 진행해서 구해야 한다.
이 문제는 운행 시간이 다른 것이 핵심이기에 마지막 순서의 아이가 놀이기구에 타는 시간을 구하는 것을 목표로 탐색을 진행한다.

이분탐색 구현

범위
- 0분부터 최대로 걸리는 시간 사이를 탐색
  - left, right = 0, max(times) * N
    - mid : 마지막 아이가 놀이기구 타는 시간
- 종료 조건
  - left가 right와 같거나 커지는 경우
- mid 시간 내에 모든 아이들이 놀이기구를 탈 수 있는지 계산
  - 탄 아이들 저장할 변수 → M 초기화 (N > M이므로)
  - 탄 아이들 수 >= N → right 감소 (시간 줄여보기)
  - 탄 아이들 수 < N → left 증가 (시간 늘려보기)

마지막 아이가 탄 놀이기구 찾기

찾은 시간으로 해당 시간까지 탑승한 아이 수 계산
운행시간에 하나씩 접근
- 비어 있는 놀이기구 확인
- 마지막 아이가 탑승했다면 해당 인덱스 + 1 값을 출력

가능한 시간복잡도

이분탐색 → $O(log(N*max(times)))$
탄 시간 계산 → $O(M)$
탄 놀이기구 확인 → $O(M)$

최종 시간복잡도
$O(log(N⋅max(times)))$ 로 최악의 경우 $O(log(2* 10^9 *30))$ 이 되어 2초 안에 계산 가능하다.

알고리즘 선택

이분탐색으로 마지막 아이가 탄 시간 계산

📌 코드 설계하기

N, M 입력
운행시간 입력
놀이기구 번호 바로 구할 수 있는 경우
아닌 경우 이분탐색 구현
4-1. 0분부터 최대 시간까지 탐색
4-2. mid까지 놀이기구를 탄 아이들 수 계산
4-3. 탑승한 아이가 N명을 초과하면 시간 감소
마지막 아이가 탄 놀이기구 찾기
5-1. 해당 놀이기구가 정확히 left 시점에 비었다면 탄 사람 추가
5-2. 마지막 아이가 탔으면 출력

📌 시도 회차 수정 사항

1회차

마지막 아이가 탄 놀이기구 번호 구하는 코드가 계속 틀렸다.
놀이기구에 탄 아이들의 수를 세는 로직이 잘못됐다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# 운행시간 입력
times = list(map(int, input().split()))

# 놀이기구 번호 바로 구할 수 있는 경우
if N <= M:
    print(N)
else:
    # 0분부터 최대 시간까지 탐색
    left, right = 0, max(times) * N

    # 이분 탐색 구현
    while left < right:
        mid = (left + right) // 2

        # mid까지 놀이기구를 탄 아이들 수 계산
        rides = M
        for time in times:
            rides += mid // time

        # 탑승한 아이가 N명을 초과하면 시간 감소
        if rides >= N:
            right = mid
        else:
            left = mid + 1

    # 마지막 아이가 탄 놀이기구 찾기
    rides = M
    for time in times:
        rides += (left - 1) // time

    for i, time in enumerate(times):
        # 해당 놀이기구가 정확히 left 시점에 비었다면
        if left % time == 0:
            rides += 1
        # 마지막 아이가 탑승한 경우 출력
        if rides == N:
            print(i + 1)
            break