백준13904 문제 보러가기

문제

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

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

입력

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

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

출력

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

예제 입력 1

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예제 출력 1

185

문제 해결 과정

문제를 보면 일단 우선순위를 정하는 게 중요하다고 생각했다.
과제의 점수를 우선순위에 두고 하면 날짜가 문제가 되고, 날짜에 우선순위를 두면 과제의 점수를 최댓값을 못 구할 것이라고 생각했다.

사실 30분 넘게 고민을 했는데 우선순위에 꽂혀서 고민을 했는데, 그러다가 블로그 하나를 봤다.
그 블로그에서의 방법을 이러했다.
과제의 점수 순으로 정렬을 하고 같은 마감일이 있으면 해당 마감일에 가장 높은 과제의 점수의 것을 해결하면 된다. 그리고 그 마감일에 체크를 하고 다음으로 넘어갔을 때 해당 마감일에 체크가 되어있으면 전날 해결하면 된다.

위를 예시를 들면, [4, 60] / [2, 50] / [4, 40] / [3, 30] / [1, 20] / [4, 10] / [6, 5] 로 먼저 정렬을 한다.
먼저 60인 것을 보면 마감일이 4일이기 떄문에 4일에 체크를 한다.
그 다음에 50인 것을 보면 마감일이 2일 이기 떄문에 2일에 체크를 한다.
그 다음에 40인 것을 보면 마감일이 4일인데, 아까 체크를 했기 때문에 전날인 3일에 체크를 한다.
이런 식으로 하다보면 마감일과 최대 과제 점수를 챙길 수 있다.

최종 코드

import heapq

N = int(input())

hq = []
max_day = 0
for i in range(N):
    d, w = map(int, input().split())
    heapq.heappush(hq, (-w, d))
    if max_day < d:
        max_day = d

assigned = [False] * (max_day + 1)

score = 0
while hq:
    w, d = heapq.heappop(hq)
    w = -w

    for i in range(d, 0, -1):
        if assigned[i]:
            continue

        assigned[i] = True
        score += w
        break

print(score)