[그리디] 백준 13904번: 과제 / 골드 3

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

13904번: 과제

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

www.acmicpc.net

import heapq
n = int(input())
lst = []
for i in range(n):
    lst.append(list(map(int, input().split())))
lst.sort()

day = lst[-1][0]  # max day
q = []
answer = 0
while day > 0:
    while lst:
        d, w = lst.pop()
        if day == d:
            heapq.heappush(q, -w)
        else:  # put it back
            lst.append([d, w])
            break
    if q:
        answer += (-heapq.heappop(q))
    day -= 1
print(answer)

우선순위큐로 풀 수 있다.

풀이의 실마리는 뒷 날짜부터 거꾸로 탐색하면서

가능한 숙제 중 가장 점수가 큰 숙제를 해결하는 것이다.

리스트를 날짜 순으로 정리한 뒤, pop()으로 하나씩 빼면서

가능한 숙제면 q에 넣는다.

그렇게 가능한 숙제를 q에 모두 넣고 나면

q에서 점수가 가장 큰 숙제를 하나 뽑아서 answer에 더해주는 방식이다.