[백준(BOJ)] 1202번 : 보석 도둑 - PYTHON[파이썬]

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

1202번: 보석 도둑

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

 

---

 

⊙ 문제 접근 과정

 

1️⃣ 보석 리스트 gem에 (무게, 가치)를 담아준다.

 

2️⃣ bag 값을 담아주고 정렬해준다.

 

3️⃣ 임시 배열인 temp를 만들어 허용 가능한 보석을 계속 넣어주고 그중 값어치 나가는 보석을 pop

 

4️⃣ pop한 값을 result 변수에 더해주고 마지막으로 result 출력

 

 

---

 

⊙ 문제 풀이

 

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())
gem = []
bag = []

for _ in range(N):
    heapq.heappush(gem, list(map(int, sys.stdin.readline().split())))

for _ in range(K):
    bag.append(int(input()))

bag.sort()

result = 0

temp = []

for b in bag:
    while gem and b >= gem[0][0]:
        x,y = heapq.heappop(gem)
        heapq.heappush(temp,-y)

    if temp:
        result -= heapq.heappop(temp)

print(result)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!