[백준] 1202 - 보석 도둑 💎 (Python) / 골드 2 / 정렬 / 그리디

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

요약하자면, 첫줄에 N(보석 개수)와 K(가방 개수)가 주어지고, 다음에 N줄에 걸쳐 보석의 무게(Mi)와 보석의 가겨(Vi)가 주어지며, 다음에 K줄에 걸쳐 각 가방의 허용 무게(Ci)가 주어집니다. 상덕이가 K개의 가방에 대해 각각 허용 무게를 지키며 보석을 훔칠 때, 최대 가격을 구하는 문제입니다. (각 가방엔 보석이 1개만 들어가고, 보석의 무게와 가격은 0이상, 가방의 허용 무게는 1이상 입니다.)

 

1) 예제 입출력❄️

예제 입출력

첫번째 예제를 보면, 보석은 2개, 가방은 1개. 각 보석의 (무게, 가격)은 (5, 10), (100, 100)이고, 가방 1개의 허용 무게는 11입니다. 가방이 1개이기 때문에 그냥 허용 무게중 최대 가격인 첫번째 보석을 훔칠 수 있고, 이 때 훔친 보석의 총 가격은 10 입니다.

 

2. 핵심 논리☢️

보석의 무게, 가격 리스트와 가방의 무게 리스트를 오름차순으로 정렬하고, 각 가방별로 훔칠 수 있는 보석을 최대힙을 통해 탐색하는게 핵심입니다. 최대힙을 쓰면, 각 보석의 무게에 대해 힙에 원소를 넣을 때 O(logN)의 시간복잡도로 정렬된 힙을 구성할 수 있습니다. 또한, 각 가방에 최대 가치의 보석을 찾는 과정 역시 O(logN)의 시간복잡도로 동작합니다. 일반적으로 N개의 정렬된 원소를 구성하고 출력하는데 O(N)의 시간복잡도에 비해 월등히 빠릅니다.

3. 풀이 코드✅

import sys
import heapq
input=sys.stdin.readline
n,k = map(int,input().split())
gems = [[*map(int,input().split())] for _ in range(n)]
bags = [int(input()) for _ in range(k)]
gems.sort();bags.sort()
result = 0;tmp = [] 

for bag in bags:
    while gems and gems[0][0] <= bag:
        heapq.heappush(tmp, -gems[0][1])
        heapq.heappop(gems)
    if tmp:
        result -= heapq.heappop(tmp)
print(result)

총 n개의 보석, k개의 가방을 입력받습니다. gems에는 [ [ 보석무게, 보석가격], …] 형태의 2중 리스트가 생성됩니다. bags에는 k개 가방에 대해 허용 무게가 저장됩니다.

gems를 보석 무게에 대해 오름차순, 보석 무게가 같을땐 가격으로 오름차순 정렬하고, bags도 오름차순 정렬합니다. result는 k개의 가방으로 훔칠 수 있는 보석 가격의 최대값이 저장될 변수이고, 0으로 초기화 합니다. tmp는 최대 힙입니다. 가방의 무게가 작은 것부터, 해당 가방으로 훔칠 수 있는 최대 보석의 가격을 탐색하는 역할을 합니다.

for 문으로 bags에서 가방의 무게를 작은 것 부터 반복합니다. 각 가방의 무게에 대해, 그 가방으로 훔칠 수 있는 보석들을 while문을 돌며 최대 힙에 저장합니다. while 문은 gems 보석 리스트가 비어있지 않고, gems에서 제일 가벼운 보석의 무게가 bag 이하이면, tmp에 마이너스를 취해서 보석의 가격을 삽입(heappush)하고, 그 보석은 gems에서 heappop 합니다. - 를 취해서 heap에 삽입하는 이유는 보석의 무게는 0 이상인데 음수로 최소힙에 저장하면, 최소값은 음수로 제일 작은 수 이고, 이는 다시 -를 취해주면 양수로 최대값이기 때문입니다. 즉, -를 취해서 최소힙을 최대힙으로 사용하는 것 입니다.

tmp가 존재하는 경우. 즉, 현재 bag 무게 이하의 훔칠 보석이 있다면, heappop으로 최대 가격의 보석을 빼서 result에 갱신합니다. 이 때, result -= heapq.heappop(tmp)를 하는 이유는 현재 힙에 보석의 가격이 음수로 저장되있기 때문입니다.

 

* 주석 달린 풀이

import sys
import heapq # 힙
input=sys.stdin.readline # 입력 빠르게
n,k = map(int,input().split())
gems = [[*map(int,input().split())] for _ in range(n)]
bags = [int(input()) for _ in range(k)]
gems.sort() # 무게 오름차순, 무게 같으면 가격 오름차순
bags.sort() # 가방 무게 오름차순
result = 0 # 결과 출력값 초기화
tmp = [] # 보석의 가격 저장 리스트

for bag in bags: # 각 가방 무게에 대해
    while gems and gems[0][0] <= bag: #제일 가벼운 보석무게를 bag이 허용하는한 반복
        heapq.heappush(tmp, -gems[0][1]) # 가격을 최대힙에 저장(음수로 저장하여 최소힙을 최대힙으로)
        heapq.heappop(gems) # 가격 저장한 보석은 버리기
    if tmp: #bag 무게 이하 보석 가격 다 저장했으면
        result -= heapq.heappop(tmp) # 제일 가치가 높은 가격 더하기(음수니까 빼기)
print(result)

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/1202_%EB%B3%B4%EC%84%9D_%EB%8F%84%EB%91%91.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

 

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/
2. 최대 힙 최소 힙 개념: https://velog.io/@jaenny/자료구조-힙-최소힙-최대힙
3. 풀이: https://velog.io/@mmy789/Algorithm-최소힙-최대힙