[골드 3] 백준 13904 - 과제 (파이썬)

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

풀이

• 각각의 과제는 마감일(d)와 점수(w)가 주어진다.
• 하루에 하나의 과제만 할 수 있다.
• 점수를 최대화 하도록 과제를 선택해야 한다.

즉, 뒤에서부터 앞으로 오면서 해당 날짜에 할 수 있는 과제 중 점수가 가장 높은 것을 선택하는 방식인, 그리디 + 우선순위 큐를 사용한다.

왜냐하면 마감일이 큰 과제부터 보되, 그 날짜에 할 수 있는 가장 점수 높은 과제를 선택해야하기 떄문이다.

우선순위 큐를 사용해 효율적으로 가장 점수가 높은 과제를 선택 할 수 있다.

N = int(input())
due = [[] for _ in range(1001)]

due[i]는 마감일이 i인 과제들의 점수 리스트를 저장한다.

1000일을 기준으로 만든 건, 문제 조건에서 최대 마감일이 1000이기 때문이다.

for i in range(N):
    d, w = map(int, input().split())
    due[d].append(w)

각 과제의 마감일과 점수를 받아서 해당 날짜 리스트에 점수를 추가한다.

for i in range(1000, 0, -1):
    for w in due[i]:
        pq.put(-w)

날짜를 1000에서 1로 역순으로 탐색하고, 해당 날짜에 마감되는 과제들을 우선순위 큐에 모두 넣는다.

또한 pq.qsize()를 통해서 우선순위 큐에서 가장 높은 점수를 꺼내어 그 날 수행한다.

시간 복잡도 분석

• O(N log N)

코드

# 백준 13904 - 과제
# 분류 - 우선순위 큐

from queue import PriorityQueue

N = int(input())

due = [[] for _ in range(1001)]

for i in range(N) :
    d, w = map(int, input().split())
    due[d].append(w)

pq = PriorityQueue()
answer = 0
for i in range(1000, 0, -1) :
    for w in due[i] :
        pq.put(-w)
    
    if pq.qsize() > 0 :
        answer += -pq.get()

print(answer)