[백준] [이분탐색] 놀이공원 : 1561 Python

이분 탐색 문제이다. 이 문제는 총 M대의 놀이기구가 있을 때, N명이 순서대로 놀이기구를 탈 때, 마지막 사람이 타게 되는 놀이기구의 인덱스를 맞추는 문제이다.

문제를 봤을 때, 프로그래머스의 입국심사와 비슷한 느낌이 있었지만, 차이점이 있다고 느꼈고 나는 입국심사를 푼 테크닉을 바탕으로 약간의 아이디어를 추가하여 이문제를 풀었다.

이문제는 N명의 사람은 빈 놀이기구에 순서대로 들어가고, 각 놀이기구 마다 소요되는 시간이 다르다. 여기서 조심해야 할 점은 입국심사와는 다르게 사람들이 최소 시간을 위해 놀이기구 선택을 하는 것이 아닌, 여러 개가 비어있다면 단순히 인덱스가 작은 놀이기구부터 탄다는 점이다.

내가 문제를 푼 아이디어는 아래와 같다.
1. N-M명을 태울 때는 최소 시간을 위해 놀이기구를 선택하는 결과와 같을 것이다. -> N-M명을 태우는 최소 시간을 이분 탐색을 통해 찾음
2. 찾은 시간을 바탕으로 몇 명을 태웠는지, 감 놀이기구가 찾은 시간을 기준으로 몇 분 동안 쉬고 있는지 구한다.
3. 놀이기구 휴식시간과 인덱스를 기준으로 정렬한 후, 마지막 사람이 타게 될 놀이기구의 번호를 구한다.

이를 코드로 구현하면 위와 같이 된다.

한 가지 주의할 점은 이분 탐색을 통해 N-M명이 타기 위해 걸리는 최소 시간을 찾게 되는데, 이것은 N-M명이 탈 수 있는 최소 시간이지 이 시간 동안 N-M명 이상도 탈 수 있기 때문에 이 시간이 있다면 탈 수 있는 인원을 다시 구해주어야 한다.

다행히 입국심사를 통해 연습이 되어 다른문제보다는 쉽게 풀 수 있는 문제였다.

문제출처 : 백준 https://www.acmicpc.net/problem/1561

1561번: 놀이 공원