[Python] [백준🥇3] 13904번 과제 (우선순위 큐, 그리디)

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

13904번: 과제

문제

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

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

입력

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

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

출력

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

풀이

우선 데이터를 입력 받을 때 제출 기한이 같은 과제들의 수를 Count에 저장 해뒀다. 그 후 제출 기한을 기준으로 최대힙을 구현한 다음, 힙에서 우선순위가 가장 높은(기한이 제일 많이 남은) 과제의 수 만큼(Count 참조) Pop하여 임시 힙에 최대 힙 형태로 저장. 그리고 나머지 힙에서 우선순위가 가장 높은 과제의 기한을 빼서 과제를 수행할 공백 시간을 구하고 그 시간만큼 임시 힙에서 Pop하고 결과에 더하기.

import sys
import heapq
input = sys.stdin.readline
n = int(input())
ass = []
# 제출 기한에 대응하는 인덱스를 가진 2차원 리스트 (1<= d <= 1000)
count = [[] for i in range(1001)]
for i in range(n):
    until, score = map(int, input().split())
    # count에 삽입
    count[until].append(score)
    # 제출 기한 기준의 최대 힙
    heapq.heappush(ass, (-until, score))
# 점수를 저장할 임시 힙
temp_ass = []
ans = 0
while ass:
    # count[-ass[0][0]] == 우선순위가 제일 높고 제출 기한이 같은 과제들 수
    for i in range(len(count[-ass[0][0]])):
        until, score = heapq.heappop(ass)
        heapq.heappush(temp_ass, -score)
    # 과제 가능한 공백 시간 day
    if ass:
        day = -until + ass[0][0]
    else:
        day = -until
    for i in range(day):
        if temp_ass:
            ans -= heapq.heappop(temp_ass)

print(ans)

다른 풀이 참조 및 개선할 점

# from dhkdwlsgod
import sys
input = sys.stdin.readline
# sys.stdin = open("input.txt", "rt")

n = int(input())

arr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b))
arr.sort(key=lambda x: x[1], reverse=True)
cnt = 0
vis = [False] * (1000 + 1)
for day, money in arr:
    j = day
    while j> 0 and vis[j]:
        j-=1
    if j == 0:
        continue
    else:
        vis[j] = True
        cnt+=money
print(cnt)

데이터를 점수 기준으로 정렬. 하루에 하나밖에 과제를 수행할 수 없는 조건을 이용하여 과제를 수행할 수 있는 날 중 (vis) 가장 높은 날짜에 대응 시키는 방식 (제출 기한이 4일, 3개면 4일, 3일, 2일)