[python] 백준 13904번 : 과제

 

 

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

난이도: G3

---

문제

---

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

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

입력

---

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

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

출력

---

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

예제 입력

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

예제 출력

185

풀이

---

우선순위 큐(최대힙)을 이용한 문제이다.

1. 주어지는 점수와 마감일수를 최대힙에 넣어주면서 max_day(남은 일수중 가장 큰값)을 갱신해준다.

2. max_day+1 만큼의 길이를 가지는 배열을 만들어 준다.(인덱싱 편하게 +1을 해줬다.)

3. 힙이 빌때까지 while문 반복

- 1) pop으로 나온 w,d중 d부터 1일까지 day배열에서 빈 부분을 찾는다.

- 2) 비어있다면, 해당 위치에 -w을 넣어준다.

4. 구해진 배열(day)의 전체합을 구하면 정답

제출코드

import sys,heapq
input=sys.stdin.readline

N=int(input())
hq=[]
max_day=0
for _ in range(N):
    d,w=map(int,input().split())
    max_day=max(max_day,d)
    heapq.heappush(hq,(-w,d))

day=[0]*(max_day+1)
while hq:
    w,d=heapq.heappop(hq)
    for i in range(d,0,-1):
        if not day[i]:
            day[i]=-w
            break
print(sum(day))

---

틀린 부분이 있거나 인용한 부분에 대해 문제가 있을 시
댓글로 알려주시면 감사하겠습니다.