[Gold III]
https://www.acmicpc.net/problem/13904
13904번: 과제
예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.
www.acmicpc.net
풀이
Greedy와 Priority Queue를 적절히 이용해 풀 수 있었던 문제.
입력된 과제를 점수(value) 순으로 정렬하고, 점수가 높은 것부터 Greedy하게 몇일차에 풀 지 배치.
7
4 60
4 40
1 20
2 50
3 30
4 10
6 5
와 같은 예제 입력에서는, 점수 순으로 정렬했을 때 아래와 같아진다.
4 60
2 50
4 40
3 30
1 20
4 10
6 5
맨 위(점수가 가장 높은것)부터 하나씩 배치하면 되는데, 가능한 한 가장 늦게 푸는 날짜를 택한다.
4 60 이므로 4일차에 풀고,
2 50 이므로 2일차에 풀고,
4 40 은 4일차에 이미 풀었으므로, 가능한 가장 늦은 날짜인 3일차에 푼다.
그 다음으로 3 30 은 3일차, 2일차가 모두 채워져 있으므로, 1일차에 푼다.
1 20 과 4 10 은 1, 2, 3, 4일차가 모두 채워져 있어 풀지 못하고, 6 5 를 6일차에 풀도록 한다.
이런 식으로 Greedy하게 풀이하면, 정답을 얻을 수 있다 ^ㅁ^
import heapq
N = int(input())
assignments = []
for _ in range(N):
a = tuple(map(int, input().split()))
a = (-a[1], a[0]) # reverse tuple (for append in Priority Queue(heapq))
heapq.heappush(assignments, a)
result = {}
while assignments:
a = heapq.heappop(assignments)
day = a[1]
while True:
if day == 0:
break
if result.get(day):
day -= 1
continue
else:
result[day] = -a[0]
break
print(sum(result.values()))