[python] 백준 13904 과제

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

13904번: 과제

 

문제 해결

• 어떻게 일을 먼저 계획할 것인지 순서를 정하는 문제
• 당연히 점수가 높은 일을 먼저 계획을 해야한다.(중요하기 때문)
• 그다음 고려할 것은 가능하면 빨리 해결해야하는 문제이다.
• 따라서 힙(heap)을 사용할 것이다.
• 그리고 가능하면 마감기간에 처리를 하여 비록 비중이 적지만 빨리 처리해야하는 것도 처리할 수 있도록 한다.

 

CODE

import sys
input = sys.stdin.readline
import heapq

def solution():
    global answer
    reservation = [0 for _ in range(1001)]
    while heap:
        sub_w, d = heapq.heappop(heap)
        # print(sub_w)
        w = -1*sub_w
        for i in range(d,0,-1):
            if reservation[i]==0:
                reservation[i] = 1
                answer += w
                # print(answer)
                break

if __name__=='__main__':
    n = int(input())
    heap = []
    answer = 0
    for _ in range(n):
        d, w = map(int, input().split())
        heapq.heappush(heap, (-w,d))
    solution()
    print(answer)