[백준 1202번] 파이썬 - 보석 도둑

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

1202번: 보석 도둑

 

 

단순 정렬을 이용하여 풀릴 것 같지만, 시간초과에 빠지는 문제이다.

 

# 조건

• 보석점을 털기로 결심한 상덕이
• 보석이 총 N개 존재하며, Mi와 Vi의 무게와 가격을 가지고 있다.
• 가방을 K개 가지고 있으며, 각 가방의 최대 무게는 Ci이다.
• 가방에는 최대 한 개의 보석
• 훔칠 수 있는 보석의 최대 가격을 구하라

 

# 입력

• 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
• 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)
• 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)
• 모든 숫자는 양의 정수이다.

 

# 접근 방법

• sort를 이용해 보석 가치기준 내림차순, 무게기준 오름차순으로 정렬해준 후 찾는다면 해결 될 것 같지만 시간초과
• 따라서, heapq를 이용해주자.
• 우선, 보석의 무게와 가치를 무게 기준 최소힙에 구성해준 후, 가방 무게를 최소힙으로 받아준다.
•  
  최대 용량이 제일 가벼운 가방부터 담을 수 있는 보석 리스트를 뽑아준 후, 제일 가치있는 보석을 담아주면 될 것 같다.
  • 이 때는, 최고 가치를 담아야 되므로 최대힙으로 구성

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

N, K = map(int, input().split())

jewel = []

for _ in range(N):
    x, y = map(int, input().split())
    # 최소힙 구성
    heappush(jewel, (x,y))

bag = []

for _ in range(K):
    a = int(input())
    # 최소힙 구성
    heappush(bag, a)

result = 0

possible = []

while bag:
    min_bag = heappop(bag)
    while jewel and min_bag >= jewel[0][0]:
        # 가방에 담을 수 있는 보석 리스트 담아주기
        heappush(possible, (-jewel[0][1], jewel[0][1]))
        heappop(jewel)

    if possible:
        # result += possible[0][1]
        # heappop(possible)
        result += heappop(possible)[1]

print(result)