[백준] 2109번 순회강연 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/2109

문제해결 아이디어

• 강연들을 날짜 순으로 오름차순정렬한다.
• 강연들을 순회하면서 최소힙을 통해 값을 추가하다가 (최소힙에 들어있는 원소의 개수) > 현재 순서의 강연날짜 인 경우
• 최소힙에 들어있는 pay 와 현재 강연의 pay를 비교해서 무엇을 버릴지 결정한다.

소스코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())

arr = []

for _ in range(n):
    arr.append(list(map(int, input().split())))

arr.sort(key=lambda x: x[1])

h = []

for pay,day in arr:
    if day > len(h):
        heapq.heappush(h, pay)
    else:
        if h[0] < pay:
            heapq.heappush(h, pay)


print(sum(h))

여담

• 다른사람의 풀이를 보다가 더욱 쉽게 표현하는 방법을 찾았다.

for pay, day in arr:
	heapq.heappush(h, pay)
    if len(h) > day:
    	heapq.heappop(h)