[백준] 13904 과제, python

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

 

처음에는 백트래킹과 dp를 사용해서 해결하려 했는데 시간초과가 났다.

힙을 사용해서 간단하게 풀수 있는 문제였다.

최소힙에 과제 점수를 넣고, 힙의 길이가 마감까지 남은 일수보다 클 경우 최솟값을 제거한다.

최종적으로 마지막까지 힙에 남은 값들을 더해주면 된다.

마감일까지 남은 일수(d)	과제점수(w)	최댓값이 되게 선택 하는 경우	설명
1	20	20	1일차에는 1개까지 가능하므로 20 추가
2	50	20, 50	마찬가지로 50 추가
3	30	20, 30, 50	30 추가
4	10	10, 20, 30, 50	10 추가
4	40	20, 30, 40, 50	4개까지 밖에 수행할수 없으므로 가장작은 10을 빼고 40을 추가
4	60	30, 40, 50, 60	마찬가지로 20을 빼고 60을 추가
6	5	30, 40, 50, 60, 5	5추가

 

import sys
import heapq
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

# 과제들을 남은 일수, 점수 순으로 정렬
arr.sort(key=lambda x:(x[0],x[1]))

heap = []

for d,w in arr:
    heapq.heappush(heap,w)  

    # 힙의 길이가 남은일수보다 길다면 최솟값 제거   
    if len(heap) > d:
        heapq.heappop(heap)
    
print(sum(heap))