[백준 2109번] 순회강연(파이썬)

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

2109번: 순회강연

그리디 문제입니다.

만약에 날짜가 겹친다면

가격을 더 쌘데 부르는 곳을 가야합니다.

 

이 문제는 우선순위 큐로 풀 수 있었습니다.

q에 페이를 넣어주되

현재 날짜가 q보다 크면

q의 가장 작은 값을 pop해줍니다.

예를들면

1 20

1 100  이렇게 들어왔다고 치면

 

1 100을 넣으면

q가 20 100 이렇게 2개가 됩니다.

그런데 day==1이므로 q의 길이가 이보다 더 큽니다.

그래서 pop을 해주면 자연스럽게

100만 남게되는 식입니다.

 

직접 코드로 보겠습니다.

 

#백준 2109번 순회강연
from heapq import heappop,heappush
N=int(input())
times=[]
for _ in range(N):
    p,d=map(int,input().split())
    times.append([d,p])

times.sort()

money=0
q=[]

for day,pay in times:
    heappush(q,pay)
    if day<len(q):
        heappop(q)
print(sum(q))

우선순위 큐를 이용할 수 있는 문제.

그리디 알고리즘에 대한 이해와 더불어서

어떻게 큐를 쓸지 공부할 수 있는 좋은 문제입니다.