[BOJ][Python] 백준 1561번: 놀이공원

1일 1PS 46일차!

📚 문제

---

골드 2

• MinHeap?
• 이분탐색

💡 풀이 과정

---

• 처음에는 MinHeap 을 생각했다.
  • 가장 짧은 시간과 그 중에서도 놀이기구 번호가 가장 낮은 것을 우선으로 하기에, (time, attraction_num) 을 heapq 에서 pop 하고 시간을 더해 다시 push 한다 생각했다.
  • 정상 동작하지만 1 ≤ N ≤ 2,000,000,000 이므로 계속 넣었다 빼는 것은 당연히 시간 초과가 발생한다.
• 이분 탐색
  • 비정상적으로 많은 입력에 대해서는 모든 동작을 따라가는 것이 아니라 범위로 탐색해야한다.
  • 범위 탐색 중 가장 대표적인 것이 이분 탐색이다.
  • N 명이 탈 수 있는 최소 시간에 대해 검색한다.
  • 이후 최소 시간 - 1 에 탈 수 있는 인원을 찾고 남은 인원만큼 놀이기구 순서대로 검사하면서 최소 시간에 운행하는 놀이기구만을 찾고 N 번째 탑승 기구를 찾는다.

📌포인트

---

• 이분 탐색
  • if mid == target 해당 코드를 집어넣게 되면 (초과, 미만, 같음) 세 가지로 검색하므로 삼분 검색이다.
  • 제대로 된 이분 검색은 (이상, 미만) 으로 검색하도록 하자.

💻 코드

---

import heapq

N, M = map(int, input().split())
time = list(map(int, input().split()))

attractions = []
for i in range(M):
    heapq.heappush(attractions, (0, i + 1))

for i in range(N - 1):
    t, a = heapq.heappop(attractions)
    t += time[a - 1]
    heapq.heappush(attractions, (t, a))

answer = heapq.heappop(attractions)
print(answer[1])

MinHeap 코드

N, M = map(int, input().split())
time = list(map(int, input().split()))

if N <= M:
    print(N)
else:
    start = 1;
    end = max(time) * N

    while end > start:
        mid = (start + end) // 2
        temp_sum = 0

        for t in time:
            temp_sum += mid // t + 1

        if temp_sum >= N:
            end = mid
        else:
            start = mid + 1

    temp_time = end - 1
    temp_sum = 0
    for t in time:
        temp_sum += temp_time // t + 1
    N -= temp_sum

    for i in range(M):
        if end % time[i] == 0:
            N -= 1
            if N == 0:
                print(i + 1)
                break

이분탐색 코드