[그리디] 백준 13904. 과제 (feat. heapq)

문제

마감기한 안에 과제를 하루에 하나씩 할 수 있을 때, 최대 점수를 구하라

다른분 코드 보고 플옸다...
하루에 하나씩 풀되, 높은 점수인 거만 고르면 되는 줄 알았는데
기한이 빠른 걸 하는 게 중요한 게 아니고 점수가 높은걸 해야하는 거였다.
예를 들어,

 

마감기한, 점수할당
1 10
3 30
3 30
3 50

으로 주어졌을 때, 1인 것부터 하는 게 아니라 3인거 3개로 채워야 함.
따라서 value로 sorting 해서 꺼내는 게 포인트였다. 어떤 분은 마감기한 끝 부터 하던데, 이 풀이가 더 의도에 부합하는 것 같다.

나는 while day 로 풀다가 실패했는데, 이 방식으로도 다시 풀어봐야겠다.

 

<틀린 거>

import sys
sys.stdin = open('.//그리디//input3.txt','rt')
import heapq

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

n = int(input())
graph = []
limit = 0

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


# graph.sort(key=lambda x : (x[0], x[1]), reverse=True)
heapq.heapify(graph)
print(graph)
day = limit
# done = [0]*1001
done = [0]*(limit+1)
score = 0
while day != -1 and graph:
    order,d,w = heapq.heappop(graph)
    for i in range(d,0,-1):
        if done[i] ==0 :
            done[i] = w
            break
    day -= 1

print(sum(done))

 

<최종>

import sys
import heapq

n = int(input())
graph = []
limit = 0

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

# graph.sort(key=lambda x : (x[0], x[1]), reverse=True)
heapq.heapify(graph)

done = [0]*1001
score = 0
while graph:
    order,d,w = heapq.heappop(graph)
    for i in range(d,0,-1):
        if done[i] == 0 :
            done[i] = w
            break
print(sum(done))

 

* 참고

https://jokerldg.github.io/algorithm/2021/06/10/assignment.html