백준 2109. 순회강연

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

2109번: 순회강연

 

얼핏 생각하면 n이 최대 1만이기 때문에 그냥 d값이 작은 강연 즉 우선 처리해야 하는 강연 중 강연료가 높은 강연을 선택해 나가면 되지 않나 싶지만, 그렇게 하면 같은 일에 강연료가 높은 여러 강연들이 모여 있는 경우 처리가 안된다.

 

1. min heap 우선순위 큐를 만들어서 선택한 강연들의 강연료를 넣어줄 것이다.

2. 같은 날들에 하는 강연들끼리 강연료를 내림차순으로 정렬해 저장한다. 

3. 그리고 각 날들별로 강연을 선택하는데 pq.size가 곧 내가 강연한 강연들의 갯수이므로 만약 pq.size가 현재 날 보다 작다면 무조건 넣어주면 되고, 그렇지 않다면 pq.top에 가장 강연료가 낮은 강연이 있으므로 pop해주고 넣어주면 된다. 

 

최종적으로 pq에는 내가 강연한 강연들의 강연료가 담겨 있으므로 모두 더해주면 답이다.