[Gold III] 과제 - 13904

문제 링크

성능 요약

메모리: 33324 KB, 시간: 96 ms

분류

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

문제 설명

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

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

입력

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

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

출력

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

---

풀이

맨 처음에는 단순히 생각했었다. 점수별로 sort하고 날짜별로 sort 하는 방식이었는데, 이 경우에는 날짜가 지난 뒤 과제를 포기하지 못하는 문제가 있었다.

두번째로 생각난 것은 점수별로 sort하고 마감일에 딱 맞춰서 제출 하도록 새로운 리스트 인덱스에 집어넣는 것이었다. 테스트 케이스처럼 마감 기간($w$)이 같고, 점수가 다른 경우에 result[:w]안에 비어있는 인덱스 중 가장 큰 인덱스에 값을 집어넣는 방식이다.

예를들어 테스트 케이스가 아래와 같을때

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

4 60과 4 40의 우선순위는 같되, result = [0, 0, 40, 60, ... , 0]처럼 저장되는 방식이다. 만약에 그 이전에 0이 없다면 포기하는 방법이다.

아이디어

코드

import heapq
lst = []
for i in range(n:=int(input())):
    n, m = map(int, input().split())
    lst.append([-m, n])

result = [0 for _ in range(1001)]
heapq.heapify(lst)
while lst:
    p = heapq.heappop(lst)
    for i in range(p[1], 0, -1):
        if result[i] == 0:
            result[i] = -p[0]
            break
    
print(sum(result))

---

회고

사실 이 방법을 사용해 맞을 수 있었던 이유는 개수가 적어서 어거지로 맞췄다 라는 생각이 좀 많이들고, 일부 경우에서 반례도 발생할 수 있을 것 같다.

반례를 찾는다면 다시 포스팅 하도록 하겠다.