백준 2109번: 순회강연 파이썬 코드(우선순위 큐)

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

#2109

import sys
import heapq

heap = []
days = [0 for _ in range(10001)]

n = int(sys.stdin.readline())

for _ in range(n):
    p,d = map(int, sys.stdin.readline().split())
    heapq.heappush(heap, [p,d])

heap2 = []
for _ in range(len(heap)):
    heap2.append(heapq.heappop(heap))

money = 0

while len(heap2) > 0:
    temp = heap2[-1]
    del heap2[-1]
    if days[temp[1]] != 0:
        while 1:
            temp[1] = temp[1] - 1
            if temp[1] == 0:
                break
            if days[temp[1]] == 0:
                days[temp[1]] = temp[0]
                money += temp[0]
                break
    else:
        days[temp[1]] = temp[0]
        money += temp[0]

print(money)

 

설명

우선순위 큐에 넣을 때 강연료를 기준으로 정렬해야한다. 그리고 그것을 다른 리스트에 pop하면서 정렬이 된 원소들을 옮겨준다.(그냥 처음부터 리스트에 받고 정렬해도 되는데, 굳이 우선순위 큐 쓰겠다고 저렇게 푼 것이다. 그냥 정렬해도 무관) 이제 while 문 안에서 리스트의 가장 뒤의 원소부터 뽑으면서 days라는 리스트에 해당 날짜에 해당하는 인덱스에 강연료를 할당해준다(그냥 1로 할당해줘도 무관). 그러면서 money라는 변수에 강연료를 계속 더해준다. 이때 넣어야하는 날짜 인덱스에 이미 값이 있다면, 강연이 잡혀있다는 것이므로, 그 인덱스보다 적은 인덱스에 할당해준다. 당연히 넣어야하는 날짜 인덱스에 아무값도 없다면 그냥 넣어도 된다.

 

문제점

문제 설명에 "각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면"이라는 문구를 못봐서, 무조건 그 날짜에 강연을 해야하는 것으로 알고 실수를 했다.