그리디(Greedy) 알고리즘 백준#1202 #골드 | "보석 도둑" | 파이썬 풀이

문제

원본 링크: https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

접근법

본 문제의 목표는 가격이 높은 보석을 최대한 많이 담되 용량이 적은 가방부터 차례대로 담는 것입니다.

이때 가방의 용량에 따른 탐색 순서를 고려하지 않으면 문제를 제대로 풀 수 없습니다.

예를 들어, 다음과 같이 (무게, 가치) 정보가 담긴 3개의 보석과 가방 2개가 있다고 가정해 보겠습니다.

여기서 가방의 용량은 무작위로 정렬되어 있는 상태라고 가정하겠습니다.

 

보석 = [(3, 50), (2, 100), (5, 70)]

가방 = [10, 3]

 

만일 용량이 10인 가방으로 가격이 가장 높은 100짜리 보석을 훔치게 되면

나머지 용량 3인 가방으로는 가격이 50인 보석밖에 훔칠 수 없습니다. 따라서 훔칠 수 있는 최대 가격은 150인 것이죠.

하지만, 만일 용량이 10인 가방으로 가격이 70인 보석을 훔치고,

나머지 용량 3인 가방으로 가격이 100인 보석을 훔치면 총 훔친 보석의 총합은 170이 됩니다.

따라서 정확하게 문제를 해결하기 위해서는 가방의 용량에 따라 보석을 훔칠 순서를 고려해야 합니다.

 

이와 더불어, 보석과 가방 개수가 각각 최대 100만 개씩이고 시간제한이 1초이기 때문에,

비싼 보석 순서대로 담아갈 수 있는 가방을 일일이 탐색하는 이중 for 문 등으로 구현하면 시간 초과 에러가 발생합니다.

 

이에 저는 힙 자료구조를 기반으로 우선순위 큐를 구현하였습니다. 

아래 소스코드와 함께 자세히 살펴보겠습니다.

소스코드

import sys
import heapq

# 보석, 가방 개수 입력
n, k = map(int, sys.stdin.readline().split())

# 보석 무게, 가격 입력
jwels = []
for _ in range(n):
    jwels.append(list(map(int, sys.stdin.readline().split())))
# 보석 무게별 오름차순
jwels.sort()

# 가방 최대 무게 입력
bags = []
for _ in range(k): 
    bags.append(int(sys.stdin.readline()))
# 가방 무게별 오름차순
bags.sort()

# 정답: 보석 가격 누적 합산용
answer = 0
# 힙 생성
jwels_heap = []
# 가방 하나씩 탐색
for bag in bags:
    # 탐색할 보석 존재 & 훔칠 수 있는 보석 존재
    while jwels and jwels[0][0] <= bag:
        # 보석 가격만 추출해 저장
        heapq.heappush(jwels_heap, -heapq.heappop(jwels)[1])
    
    # 훔칠 수 있는 보석이 있는 경우
    if jwels_heap:
        # 보석 가격 합산
        answer -= heapq.heappop(jwels_heap)
    
    # 모든 보석을 탐색했거나 가방에 넣을 수 있는 보석이 없는 경우
    elif not jwels:
        break

print(answer)

19번째 줄에서, 가벼운 가방부터 보석을 담아갈 수 있는지 파악하기 위해 오름차순 정렬하였으며,

반복문을 통해 보석을 차례로 탐색하는 코드를 작성하였습니다.

 

28번째 줄에서, while 문을 통해 전체 보석에서 탐색이 가능하며 훔칠 보석이 존재하는지 탐색합니다.

조건을 만족하면, 최대 힙(Max heap)을 활용해 가격이 높은 보석의 가격 정보를 힙에 저장합니다.

최대 힙을 구현하기 위해 힙 앞에 음의 부호를 붙였습니다.

 

35번째 줄에서, 훔칠 보석 정보가 있을 경우 해당 보석 정보를 추출하고 가격 정보는 정답에 누적 합산해 줍니다.

그리고 만일 탐색할 수 있는 보석이 없거나 가방에 넣을 수 있는 가방이 없다면,

가방 용량별로 순서대로 탐색하는 반복문은 즉시 종료하고 정답을 출력해 줍니다.

---

오늘은 우선순위 큐를 기반으로 그리디 알고리즘 문제를 풀어봤습니다.

더 좋은 아이디어가 있으시거나 포스팅 내용에 오류가 있을 경우 아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다 ^_^

고맙습니다.