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

www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

문제풀이

N, K : 입력값

arr, bag : 보석 정보, 가방 무게

idx : arr 리스트 인덱스

 

백준 2109 순회강연 문제풀이와 유사한 문제이다. 우선순위 큐를 이용해서 현재 가방 무게에서 가능한 가장 큰 값어치의 보석을 더하는 그리디 알고리즘 방식으로 해결할 수 있다.

 

1. 보석 정보 및 가방 무게 정렬하기

 

2. 각 가방에 대해서, 현재 가방 무게를 기준으로 가능한 보석을 우선순이 큐(hq)에 넣어주기

- 가능한 보석 중 가장 큰 값의 보석을 결과(ans)에 더해주기

 

코드

import sys
import heapq

if __name__ == '__main__':
    N, K = map(int, sys.stdin.readline().split())
    arr, bag = [], []
    hq = []
    for _ in range(N):
        m, v = map(int, sys.stdin.readline().split())
        arr.append((m, v))
    for _ in range(K):
        bag.append(int(input()))
    arr = sorted(arr, key=lambda x: x[0])
    bag.sort()
    idx, ans = 0, 0
    for i in range(K):
        while idx < N and bag[i] >= arr[idx][0]:
            heapq.heappush(hq, (-arr[idx][1], arr[idx][0]))
            idx += 1
        if hq:
            value, weight = heapq.heappop(hq)
            value = -value
            ans += value
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!