[백준`G3] 13904 - 과제 (Python)

문제 설명

 

 

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

13904번: 과제

 

성능 요약

 

 

메모리: 33188 KB, 시간: 80 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬

제출 일자

2024년 4월 16일 01:38:09

문제 설명

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

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

입력

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

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

출력

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

---

문제 풀이

 

처음에는 마감일이 제일 많이 남은 순으로 정렬해서 날짜를 하나씩 줄여가며 점수가 제일 큰 값을 더하는 방법을 생각했는데...

마감일이 남았을 때의 점수들 다 고려해야 돼서 복잡한 것 같아 다른 방법을 생각했다.

 

우선순위 큐를 사용해서 점수 기준(내림차순)으로 넣어주었고,

점수가 큰 과제부터 pop을 하면서 최대한 마감일에 가깝게 과제를 처리하도록 해주었다.

이미 마감일에 처리해야 할 과제가 있다면 마감일 전날 과제를 처리하고,

마감일 전날에도 처리해야 할 과제가 있다면 마감일 전전날 과제를 처리하고,, 이런 식으로 구현했다.

import heapq

N = int(input())
heap = []
max_day = 0
ans = 0

for _ in range(N):
    d, w = map(int, input().split())
    max_day = max(max_day, d)
    heapq.heappush(heap, (-w, d))

assign = [False] * (max_day + 1)

while heap:
    w, d = heapq.heappop(heap)

    for i in range(d, 0, -1):
        if not assign[i]:
            assign[i] = True
            ans += -w
            break
print(ans)