[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 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는 과제의 점수를 의미한다.

[출력]

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

 

[아이디어]

1) 마감일이 빠른 순서대로 문제를 풀면서, 이후에 더 가치 있는 문제가 등장하면 지금까지 푼 문제 중 가장 가치가 작은 문제를 버리고 해당 문제를 푸는 것을 선택한다.

2) 과제의 마감일보다 현재까지 큐에 담은 과제가 많아지는 경우 1개를 pop하면 된다.

3) 가치 순으로 과제를 저장해야하니 우선순위 큐를 사용해야 한다.

 

from heapq import *
n=int(input())
a=[tuple(map(int,input().split())) for _ in range(n)]
q=[]
cnt=0
for d,w in sorted(a):
    if d>cnt:
        heappush(q,w)
        cnt+=1
    elif q[0]<w:
        heappop(q)
        heappush(q,w)
print(sum(q))

처음 풀 때는 위처럼 현재 개수를 따로 count하고, 필요한 경우에만 pop하도록 코드를 구현했는데 같은 맥락을 좀 더 간결하게 표현하면 아래와 같다. 일단 담고나서 담은 과제의 마감일과 현재 큐에 담아놓은 개수를 비교하여, 더 많은 경우에만 pop하면 동일한 기능을 하게 된다.

from heapq import *
n=int(input())
a=[tuple(map(int,input().split())) for _ in range(n)]
q=[]
for d,w in sorted(a):
    heappush(q,w)
    if d<len(q):heappop(q)
print(sum(q))