[백준] 13904번 과제 - 파이썬/그리디, 우선순위 큐

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

import heapq

N = int(input())

S_list = []

for i in range(N):

    D,W = map(int,input().split())

    S_list.append((W,D)) # 최대힙을 만들기 위해 순서를 반대로 넣었다.

heapq.heapify(S_list)

max_S_list = [] # 최대힙

for i in S_list:

    heapq.heappush( max_S_list, ( -i[0] ,i[0],i[1] ) )

sum = 0

for i in range(N,0,-1):
    recycle = []
    while max_S_list:

        elem = heapq.heappop(max_S_list)

        if elem[2] >= i:
            sum += elem[1]
            max_S_list += recycle
            heapq.heapify(max_S_list)
            break

        else:
            recycle.append(elem)

        if not max_S_list:
            max_S_list = recycle
            break

print(sum)

해당 문제는 뒤에서부터 채워나가야 한다.

예제 입력을 점수 최대힙으로 정렬해보면 N=7이고

[ (4,60), (2,50),(4,40),(3,30),(1,20),(4,10),(6,5)] 의 순서로 정렬된다.

그럼 이 힙큐에서 하나씩 추출해서 마감기한이 N보다 크거나 같은지 확인하고, 조건에 해당되는 과제가 나온다면 N=N-1에서 다시 같은 과정을 반복한다.

N = 7일때, N보다 마감기한이 크거나 같은 과제는 없다.
N = 6일때, (6,5)
N = 5일때, 없음
N = 4일때, (4,60)
N = 3일때, (4,40)
N = 2일때, (2,50)
N = 1일때, (3,30)

힌트로 5->4->2->1->7번순으로 과제를 수행한다고 나와있는데 N이 1일때부터 순서와 똑같다.

참고로 힙큐에 리스트연산을 하면 힙큐가 풀려서 다시 heapify를 해야한다.