(Python3) - 백준(BOJ) 1561 : 놀이 공원

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

이분 탐색 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

탑승자 아이들의 수 child, 놀이기구 수 attractions, 각 놀이기구별 탐승시간 ride_times선언 후 입력 받습니다.

📔 풀이과정

무엇에 대해 이분탐색을 해야하는지 찾기가 쉽지 않았습니다. 처음 탑승할 아이의 수가 많기 때문에 그 숫자에 힌트를 얻어 아이에 대해 이분탐색을 진행했으나 각 놀이기구마다 탐승 가능한 아이의 수가 제각각 다르기 때문에 반대로 특정 시간(last_time)이 지났을 때 누적된 탑승자 수가 입력 받은 child값과 일치하는지 확인하는 방식으로 접근해야합니다.

 

1. 이분 탐색을 진행해줍니다.

 

  1-1. left와 right변수를 설정해 시간을 이분 탐색합니다. left는 0으로 right는 충분히 큰 값(20억 * 30)으로 초기화힙니다.

 

  1-2. 해당 범위는 각 놀이기구가 한 아이를 태우는 데 걸리는 최대 시간만큼 잡았습니다.

 

  1-3. 이분 탐색 중간 지점 mid를 선언 후 구해주고 각 놀이기구가 mid시간 동안 몇 명의 아이를 태울 수 있는지 계산합니다. ride_times를 O(M)으로 순회하면 구할 수 있습니다. loop를 수행하며 mid // 각 놀이기구의 시간 값을 더해 지역변수 passenger에 더해줍니다.

 

  1-4. passenger >= child라면 탑승자가 줄어도 되므로 시간을 줄여줍니다. right = mid - 1로 갱신하며 last_time값을 mid로 저장합니다. child값과 같을 때 last_time이 정확히 mid여야 하기 때문입니다. 반대로 passenger가 child보다 작으면 left를 늘려 더 많은 탑승자가 탈 수 있도록 해줍니다.

 

2. last_time에서 정확한 탑승 위치를 찾습니다.

 

  2-1. 이분 탐색 이후에 last_time에 해당하는 시간 직전에서의 누적 탑승자 수를 계산합니다.    2-2.last_time에서 각 놀이기구가 나머지 없이 탑승 가능한지 확인해 child번째 아이가 탑승하는 놀이기구의 번호를 찾습니다. 이는 각 놀이기구의 탑승 시간  ride_times에 대해 for loop를 수행하며 last_time을 각 시간으로 나눠떨어지면 passenger를 추가시키고 이 때 값이 child와 일치하면 해당 놀이기구 번호를 반환하면 됩니다.

📔 정답 출력 | 반환

last_time기점으로 마지막 탑승자가 탔을 때 놀이기구 번호를 반환합니다.

---

📕 Code

📔 Python3

import sys
input = sys.stdin.readline

def find_time(child, attractions, ride_times):
    if child <= attractions:
        return child
    left, right = 0, 2000000000 * 30
    last_time = 0
    while left <= right:
        mid = (left + right) // 2
        passenger = attractions
        for time in ride_times:
            passenger += mid // time
        if passenger >= child:
            last_time = mid
            right = mid - 1
        else:
            left = mid + 1
    passenger = attractions
    for time in ride_times:
        passenger += (last_time - 1) // time
    for i, time in enumerate(ride_times):
        if last_time % time == 0:
            passenger += 1
        if passenger == child:
            return i + 1
    return -1
     
child, attractions = map(int, input().split())
ride_times = list(map(int, input().split()))

print(find_time(child, attractions, ride_times))

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.