[백준] 1202번 - 보석 도둑 / 골드 2 / 파이썬 풀이

문제 링크

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

1202번: 보석 도둑

 

시간 제한 : 1초

메모리 제한 : 256 MB

 

문제 요약

• 상덕이는 세계적인 도둑. 보석점을 털거다.
• 보석점에는 보석이 총 N개 있음. (입력으로 주어짐)
• 각 보석은 무게 M(i) 와 가격 V(i) 임(둘 다 입력으로 주어짐).
• 상덕이는 가방을 K개 가지고 있고, 각 가방의 최대 무게는 C(i) 임. 각 가방은 한 개의 보석만 담을 수 있음. (둘 다
  입력으로 주어짐)
  
  
• 문제 : 상덕이가 훔칠 수 있는 보석의 최대 가격은?
  
  
• 종료 조건
  - 가방을 다 사용했다면 종료.
  - 가방은 남았지만, 보석점의 보석을 다 담았다면 종료.

 

 

입력

예제 입력 1

2 1
5 10
100 100
11

예제 입력 2

3 2
1 65
5 23
2 99
10
2

 

출력

예제 출력 1

10

예제 출력 2

164

---

풀이

 

"무게가 가장 작은 가방부터 채워야 한다!"

import sys
import heapq

N, K = map(int, input().split())	# N, K 를 입력 받음.

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]:		# jewelryList[0][0] : 보석의 무게
        heapq.heappush(temp, -jewelryList[0][1])  # Max heap	# jewelryList[0][1] : 보석의 가격
        heapq.heappop(jewelryList)

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

print(-result)

 

참고

https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-1202-%EB%B3%B4%EC%84%9D-%EB%8F%84%EB%91%91-Python

[백준 1202] 보석 도둑 (Python)

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)] 보석 도둑 / 우선순위 큐