[Python] 백준 13904 과제

 

문제

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

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

 

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

 

 

 

 

 

 

 

난이도

골드3

 

 

 

 

 

내 코드

import sys
import heapq

n = int(sys.stdin.readline())
task = []
heap = []
score = 0
heapq.heapify(heap)
for _ in range(n) :
    d, w = map(int,sys.stdin.readline().split())
    task.append((d,w)) # 남은일수, 과제점수

task.sort(key= lambda x: -x[0])
i = task[0][0]
j = 0

while i > 0 :
    while j < n :
        if task[j][0] >= i :
            heapq.heappush(heap, -task[j][1])
            j += 1
        else :
            break

    if heap :
        s = heapq.heappop(heap)
        score += s

    i -= 1

print(-score)

 

 

 

 

 

풀이과정

이 문제는 우선순위 큐 문제로 첫 번째 날부터 할 과제를 정하는게 아니라 거꾸로 생각하여 마지막날부터 할 과제를 차례로 구하니 쉬웠다.

뒤에서부터 남아있을 수 있는 과제를 찾아 그 중에서 가장 높은 점수를 얻을 수 있는 과제를 그 날 푸는 것이다.

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

이 케이스로 예를 들면

6일 째에는 어차피 5점짜리 과제만 할 수 있으니 이걸 하는거고,

5일 째에는 아무것도 할 수 없다.

4일 째에는 10, 40, 60 점의 과제를 할 수 있기 때문에 이것들을 최소힙에 삽입하고 점수가 가장 높은걸 pop해서 가져온다.

3일 째에는 남은 10, 40 에 30점 짜리를 추가로 삽입하고 이 중 점수가 높은 40점 짜리 과제를 해결한다고한다.

 

이런식으로 풀면 쉽게 풀 수 있다!