[백준 13904] 과제

Junyoung Park·2022년 4월 11일
0

코딩테스트

목록 보기
356/631
post-thumbnail

1. 문제 설명

과제

2. 문제 분석

우선순위 큐를 통해 현 시점에서 가장 큰 점수를 가진 과제를 뽑을 수 있다. 이때 과제를 할 수 있다면 가장 늦게 하고, 그렇지 못하다면 하지 않는다.

3. 나의 풀이

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
pq = []
last_day = 0
for _ in range(n):
    d, w = map(int, sys.stdin.readline().rstrip().split())
    last_day = max(last_day, d)
    heapq.heappush(pq, [-w, d])
    # 점수가 가장 큰 과제부터 시작한다.

assigned = [False for _ in range(last_day+1)]
total = 0

while pq:
    w, d = heapq.heappop(pq)
    w *= -1

    for day in range(d, 0, -1):
        if not assigned[day]:
            assigned[day] = True
            total += w
            break
            # 현재 가장 큰 점수의 과제는 w. w를 가장 천천히 할 수 있을 때 한다.
print(total)
profile
JUST DO IT

0개의 댓글