[BOJ] 1202 보석도둑

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

틀린 문제 다시 풀다가 다시 못 푼 문제이다. 처음에는 문제 잘못 읽어서 가방이 하나인 줄 알았는데 가방이 여러 개였다. 여기서부터 꼬이기 시작했다.

해결

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

n, k = map(int, input().split()) #보석, 가방
gems = []
for _ in range(n):
  heappush(gems, list(map(int, input().split())))
bags = sorted([int(input()) for _ in range(k)])

ans = 0
heap = []
# 무게 작은 보석 중 가장 가치 높은 것 넣고
for b in bags:
  while gems and gems[0][0] <= b:
    heappush(heap, -heappop(gems)[1])
  if heap:
    ans -= heappop(heap)
print(ans)

이전 코드를 참고해서 풀었다. 가장 작은 가방부터 시작해서 들어갈 수 있는 최대의 가치를 넣는 방식으로 풀었다. 보기에는 n^2인 것처럼 느껴졌으나 실상은 n+n인 것 같다. heap으로 다 옮겨지면 더 이상 gems에서 뽑는게 없게 돼서 그런 것 같다.

나중에 다시 또 풀어봐야겠다.