[코테] 백준 그리디 13904번 문제

13904번 : 과제

문제 링크

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

문제 설명

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

문제 풀이

백준 1781번과 동일한 문제이다.

from heapq import heappush, heappop

n = int(input())
arr = []

for i in range(n) :
    deadline, point = map(int, input().split())
    heappush(arr, (deadline, -point))
    
solve_arr = []

for i in range(n) :
    deadline, point = heappop(arr)
    
    # 현재 저장한 배열의 길이보다 현재 데드라인이 더 크다면 저장할 수 있는 여유가 있기에 저장
    if len(solve_arr) < deadline : 
        heappush(solve_arr, -point)
    
    # 1. 현재 데드라인이 저장된 배열의 길이보다 크거나 같고
    # 2. 현재 문제를 풀었을 때 얻을 수 있는 점수가 이전 저장한 배열의 점수보다 더 많다면 교체 
    elif solve_arr[0] < -point : 
        heappop(solve_arr)
        heappush(solve_arr, -point)    

print(sum(solve_arr))