[백준 문제풀이] 얼렁떵땅 2109번 순회강연 풀이

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

 

import heapq

n = int(input())
array = [list(map(int,input().split())) for i in range(n)]
array.sort(key=lambda x:x[1])

temp = []

for pay, day in array :
	heapq.heappush(temp,pay)
	if len(temp) > day :
		heapq.heappop(temp)
print(sum(temp))

 

우선순위 큐 하는 법 잘 모른다 ㅎㅋ

그래서 이거 많이 연습해야겠다.

근데, 이거 이해하다가 너무 이해 안되어서 손으로 완전이진트리 그리면서 이해했다.

나는 똥멍청이다 ㅜ

 

그냥 우선순위 큐에서 외우면 되는 것은, 루트노드에 무조건 제일 작은수가 들어간다는것

그래서 heappop() 맨 위에 있는거 제거해 주세요 하면 가장 작은수가 제거된다.

그렇지만, 저기 위에 코드 기준 temp에 무조건 오름차순으로 있는 것은 아니라는 것

상위 노드 밑에 있는 노드는 상위 노드보다 작기만 하면 되기 때문에, 왼쪽 하위노드가 오른쪽 하위노드보다 반드시 작아야 한다거나 이런 조건은 없기 때문이다.

 

그리고 코테를 보면서 느낀점은

DP 문제가 진짜 많이 나오는 듯하다

근데, DP 문제를 내가 잘 못푸는게 문제인데 ㅎㅋ

무튼무튼무튼 그렇다는 뜻