[백준][그리디] 보석 도둑

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

1202번: 보석 도둑

 

내가 작성한 코드

import sys
from heapq import heappush, heappop

read = sys.stdin.readline

def read_data():
    N, K = map(int, read().rstrip().split())
    jewelry = []
    packs = []
    for _ in range(N):
        heappush(jewelry, tuple(map(int, read().rstrip().split())))
    for _ in range(K):
        packs.append(int(read().rstrip()))
    return jewelry, sorted(packs)

jewelry, packs = read_data()

answer = 0
pq = []
for pack in packs:
    while jewelry and jewelry[0][0] <= pack:
        m, v = heappop(jewelry)
        heappush(pq, -v)

    if pq:
        answer += -heappop(pq)

print(answer)

• 우선순위 큐
  
  • 무게가 작은 가방부터 탐색
  • 무게가 작은 보석부터 탐색
  • 현재 가방에 담을 수 있는 보석이면 최대힙에 push
  • 더 이상 가방에 담을 수 있는 보석이 없으면 최대힙에서 최대값 answer 더하기

 

다른 사람이 작성한 코드

import heapq
import sys

N, K = map(int, sys.stdin.readline().split())

jewelryList = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
bagList = [int(sys.stdin.readline()) for _ in range(K)]
jewelryList.sort()
bagList.sort()

result = 0
temp = []

for bagWeight in bagList:
    while jewelryList and bagWeight >= jewelryList[0][0]:
        heapq.heappush(temp, -jewelryList[0][1])  # Max heap
        heapq.heappop(jewelryList)

    if temp:
        result += heapq.heappop(temp)
    elif not jewelryList:
        break

print(-result)

• 아래 블로그에서 위 코드를 참고하여 작성함

https://kyoung-jnn.tistory.com/entry/%EB%B0%B1%EC%A4%801202%EB%B2%88%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EB%B3%B4%EC%84%9D-%EB%8F%84%EB%91%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90

[백준/1202번/파이썬(Python)] 보석 도둑 / 우선순위 큐

기억해야할 것

• 그리디 문제
  
  • 그리디 문제 설계에 서툴은 것 같음
  • 최대/최소 문제에서 우선순위 큐를 이용