[백준] 13904 - 과제 (Python)

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

 

 

---

 

해결

greedy 알고리즘을 어떤식으로 정렬할지가 핵심이다.

 

처음에는 점수가 높은 순으로 정렬하고 큐를 만들어, 높은 점수의 마감일을 기준으로 마감일이 적으면 왼쪽으로 추가, 마감일이 더 남았으면 오른쪽으로 추가하는 방식으로 진행을 하였다.

 

하지만 그렇게 정렬하면 오류가 있다.

 

예를 들어, (마감일 4, 점수 100), (마감일 1, 점수 30), (마감일 1, 점수 20) 과제가 있다고 가정해 보자

 

내가 처음 짠 알고리즘대로라면

 

(마감일 4, 점수 100)를 기준으로 왼쪽에 마감일 (마감일 1, 점수 30), (마감일 1, 점수 20)이 모두 등록되게 되고, 마감일이 지나버린 과제도 점수에 추가가 된다.

 

 

제대로 된 해결방법은 마감일이 많이 남은 순서대로 정렬하는 것이다.

 

 

마감일이 가장 큰 날부터 작은 날까지 반복문을 돌리면서, 4일에 할 수 있는 과제중 제일 점수가 높은 과제, 3일에 할 수 있는 과제중 점수가 높은 과제... 1일에 할 수 있는 과제중 점수가 높은 과제 를 골라주는 방식이고, 이 방식은 최대힙 을 이용하는 것이 효율적이다.

할 수 있는 과제들을 힙에 저장한 후 바로 가장 높은 점수를 반환할 수 있기 때문이다.

 

 

 

코드

 

import sys
from collections import deque
import heapq

input = sys.stdin.readline

n = int(input())
arr=[]
for _ in range(n):
    d, w=map(int, input().split())
    arr.append((d, w))

arr.sort(key=lambda x:(-x[0], -x[1]))

day=arr[0][0]
ans=0
heap =[]
index=0

for i in range(day, 0, -1):
    while index<n and arr[index][0]>=i:
        heapq.heappush(heap, -arr[index][1])
        index+=1
    if heap:
        ans+=-(heapq.heappop(heap))

print(ans)