백준: 2109 순회강연

문제

2109번: 순회강연

 

문제 풀이

 강연을 할 수 있는 경우에 따라, 시간과 일수가 정보로 주어진다. 문제를 풀기 위해서는 `heapq`를 사용하면 쉽게 해결할 수 있다. 입력된 정보(강의료, 일정)를 일정 순으로 정렬하고, heap에 있는 값의 수를 일정이라고 생각하여 처리하면 쉽게 풀 수 있다.

 

코드

from sys import stdin
import heapq


if __name__ == '__main__':
    PAY, DAY = 0, 1
    answer = 0
    n = int(stdin.readline())
    info = [list(map(int, stdin.readline().split())) for _ in range(n)]
    info.sort(key=lambda x: x[1])

    heap = []

    for i in range(n):
        answer += info[i][PAY]
        heapq.heappush(heap, info[i][PAY])

        if len(heap) > info[i][DAY]:
            answer -= heapq.heappop(heap)

    print(answer)