(파이썬 python) 백준 13904번 : 과제(greedy)

점수가 큰 과제를 뒤에서부터 채워나가는 방법으로 과제를 해결하도록 계획을 세워야 한다.

(처음엔 점수가 큰 과제부터 한다거나 마감일이 빠른 과제부터 끝내는 방법을 생각해보았지만 답은 아니었다.)

 

마감일 | 점수

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

 

이렇게 과제와 마감일이 주어져있을 때 가장 점수가 높은 과제부터 마감일부터 뒤로 계획을 세워준다.

60점 과제는 4일째

50점 과제는 2일째

40점 과제는 4일째에 이미 60점짜리를 해야하므로 3일째

30점 과제는 3일째, 2일째 이미 다른 과제가 있으므로 1일째

20점,10점 과제는 남은 기간이 없으므로 패스

5점 과제는 6일째

이런 식으로 

 

이런 알고리즘을 구현하는 데엔 heap 자료구조를 사용하는 것이 유용하다.

우선 점수가 가장 높은 과제부터 시작해야 하므로 정렬이 필요하다.

heapify함수로 list를 heap자료구조로 바꿔줄 수 있다. 

heap은 최소 힙 형태로 정렬해주며 중간에 값을 빼고 추가할 때도 자동으로 최소 힙 형태로 정렬 해준다.

이 문제에선 최소 힙이 아니라 최대 힙을 만들어주어야 하므로 첫번째 인덱스 값에 -부호를 같이 주어 최대힙을 만들어준다.

 

# 13904번 : 과제

import heapq

n = int(input())

li = []
sums = [0] * 100001
for i in range(n):
    d,v = list(map(int,input().split()))
    li.append([-v,d,v])

heapq.heapify(li)

while li:
    temp = heapq.heappop(li)
    for i in range(temp[1],0,-1):
        if sums[i] == 0:
            sums[i] = temp[2]
            break

print(sum(sums))

# https://kkk4872.tistory.com/138