최대힙 (1) 썸네일형 리스트형 [백준] 1202 "보석 도둑" -python 알고리즘 가방 무게를 오름차순으로 정렬하면서 차례대로 순회하고 이때 가방 무게보다 작은 w를 가진 보석을 모두 최대힙에 넣어둔 뒤 각 차례마다 최대힙에서 pop연산을 수행하면 그리디하게 각 단계에서의 최선의 경우를 뽑을 수 있다. 핵심은 힙에 들어가 있는 보석들은 다음 순회때도 무조건 포함될 수 있기 때문에 수행 가능한 알고리즘이다. 소스코드 # 보석 도둑 import heapq import sys n, k = map(int, sys.stdin.readline().split()) items = [] for _ in range(n): w, v = map(int, sys.stdin.readline().split()) items.append([w, v]) bags = [] for _ in range(k): b.. 이전 1 다음
