(Python) 백준 1202. 보석 도둑

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

문제보기

---

from sys import stdin; input=stdin.readline
import heapq

N, K = map(int,input().split()) # 보석갯수 N, 가방갯수 K
jewels = [] # 보석의 (무게,가치)로 리스트 만들기
for _ in range(N):
    heapq.heappush(jewels, list(map(int,input().split()))) # 힙으로 보석 집어넣기

bags = [ int(input()) for _ in range(K)] # 가방의 허용무게로 리스트 만들기
bags.sort()
que = []
res = 0
for bag in bags:
    while jewels and bag >= jewels[0][0]: # 보석이 있고, 가방에 들어가는 크기일 때
        val = heapq.heappop(jewels)[1] # (들어가는)가치 뽑아내기
        heapq.heappush(que, -val) # 큐에 저장해두기
    if que: # 큐에 다 집어넣고 난 후, 큐에 값이 있으면
        res -= heapq.heappop(que) # 결과값에 더해주기
    elif not jewels: # 큐에 값이 없는데, 남은 보석도 없는 경우, 가방에 넣을 수 있는 보석이 없다는 것
        break

print(res) # 결과값 프린트

문제 풀이

• 힙큐와 정렬을 사용해서 푸는 문제. 처음에는 보석을 순회하면서 가방에 집어넣으려고 했는데, 한참을 막혀 가방을 순회하는 방식으로 돌아갔다.
• 보석을 최소힙에 넣어둔다.
• 가방은 하나의 값으로 들어오기 때문에, sort를 이용해서 정렬해둔다.
• 가방을 순회하면서, 보석이 있고 가방의 수용용량이 보석의 크기보다 크면 최대힙에 집어넣는다.
• 순회한 이후, que에 있는 "가장 큰 값"을 결과값에 더해준다.
• que가 비었고 보석이 없다면, 이제 가방에 넣을 수 있는 보석이 없다는 뜻이니 순회를 종료한다.

틀린 코드

from sys import stdin; input=stdin.readline
import heapq

N, K = map(int,input().split()) # 보석갯수 N, 가방갯수 K
jewels = [tuple(map(int,input().split())) for _ in range(N)] # 보석의 (무게,가치)로 리스트 만들기
jewels.sort()
bags = [tuple((0, int(input()))) for _ in range(K)] # 가방의 허용무게로 리스트 만들기
bags.sort()
max_weight = bags[-1][1] # 최대허용무게 설정해두기. 이거보다 크면 바로 컨티뉴
tot_val = 0 # 넣을 수 있는 보석가치 합산할 변수. 안쓸수도 있음(이게베스트)
for wei, val in jewels:
    if wei > max_weight: # 최대무게보다 크면 컨티뉴
        continue
    if val <= bags[0][0]: # 최소가치보다 작아도 컨티뉴
        continue
    else: # 위의 경우가 아니라면 꺼내가며 비교해야 함.
        while bags: # 계속 꺼내가며 반복해야 하기 때문에 while 사용
            xx, yy = heapq.heappop(bags)
            if yy >= wei: # 만약 가방에 바로 넣을 수 있는 상황이면
                heapq.heappush(bags, (val, yy)) # 바로 넣어버림
                break
            else: # 만약 현재 가방이 허용하는 무게보다 더 큰 보석이면
                # 보석은 무게로 정렬해두었기 때문에, 이제 그 가방에 다른 보석이 들어갈 일이 없어짐
                # 그렇기 때문에 해당 가방은 이제 킵. 토탈밸류에 저장해놓음
                tot_val += xx

for va, we in bags: # 가방에 남은 보석들 가치 합산하기
    tot_val += va

print(tot_val)