1 minute read

1202번 : 보석 도둑

문제 링크

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

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

문제 풀이

위 캡처에서 봤듯이 테스트 케이스는 다 통과했으나 시간초과로 통과하지 못하여 결국 질문 게시판에 있는 다른 사람들의 답변을 참고하였다.

다른 사람들은 heapq를 사용하였다는 것인데 이진 트리에 원소를 추가하는 heapq는 O(log(n))의 시간 복잡도로 훌륭한 효율을 보여준다.

오른쪽은 참고한 웹페이지 링크 : https://www.daleseo.com/python-heapq/

from heapq import heappush, heappop
import sys

input = sys.stdin.readline

n, k = map(int, input().split())
gems = []
bags = []
car_gems = []
result = 0

# heappush를 이용하여 힙에 원소를 추가한다. 
for _ in range(n) :
    heappush(gems, list(map(int, input().split())))

# heappush를 이용하여 힙에 원소를 추가해도 heappop을 이용하지 않으면 정렬 X
# bag은 따로 sort를 이용하여 정렬
for _ in range(k) :
    heappush(bags, int(input()))
bags.sort()

# bag의 원소들을 꺼내 반복
for bag in bags : 
    
    # gems 원소가 있고, gems 중 가장 무게가 적게 나가는 것과 가방의 무게를 비교하여 가방이 더 클때 안에 내용 진행
    # heap[0]을 사용하면 가장 작은 원소를 반환한다.
    while gems and bag >= gems[0][0] :
        # car_gems에 무게가 가장 적게 나가는 보석의 가격을 저장
        # -heappop을 붙인 이유는 가격이 큰 순으로 정렬하기 위해
        heappush(car_gems, -heappop(gems)[1])
    
    # car_gems에 원소가 있을때 안에 내용 진행
    if car_gems : 
        # result에 가격이 가장 나가는 가격을 더함
        result += -heappop(car_gems)
    
    # gems 원소가 없으면 반복문 나가기
    elif not gems : break
        
print(result)

Comments

You May Also Enjoy