https://www.acmicpc.net/problem/13904
13904번: 과제예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.www.acmicpc.net
2가지 풀이가 있음
힙으로 푸는건 순회공연때 해봤으므로, 그리디로 풀어봄(정답코드참고함)
먼져, 숙제를 무조건 w가 큰 순서로 정렬한다
그리고, 가장 좋은경우
즉 숙제를 할 수 있는 마지막 날에 숙제를 한다고 생각한다.
만일, 숙제를 할 수 있는 마지막날에 이미 숙제를 했다면, day를 1씩 줄여나가면서 가능한 날짜를 찾는다
(w기준으로 최대값부터 탐색을 하면서 가능)
만일 숙제를 할 수 없다면 어쩔 수 없고, 할 수 있다면 정답값에 더해준다.
import sysinput = sys.stdin.readlinen = int(input())hw = []
visit = [False] * 1001for _ in range(n): d, w = map(int, input().split())
hw.append((d, w))
hw.sort(key=lambda x: x[1], reverse=True) # 무조건 weight가 크게 정렬함answer = 0
for d, w in hw: while d > 0 and visit[d]: # 과제를 할 수 있는 최대한의 날짜를 찾는다
d -= 1 # 처음d값은 날짜이고, 이후 d날에 이미 과제를 했다면 그전 과제를 할 수 있는 날짜를 구한다..
if d: # 만일 과제를 할 수 있을경우 (w기준 최댓값순으로 정렬했으므로)
visit[d] = True # 그날에 과제를 한다. answer += wprint(answer)힙
import sysfrom heapq import heappush, heappopinput = sys.stdin.readlineh = []
hw = sorted([[*map(int, input().split())] for _ in range(int(input()))])
for d, w in hw: heappush(h, w) if d < len(h): heappop(h)
print(sum(h))