[BOJ] 1202. 보석도둑

 

www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

문제: 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하라.

 

문제 이해하기!!

각 보석의 무게와 가격이 있고, 보석 넣을 가방에는 보석 한 개씩 밖에 못 넣으며, 무게 한도가 있다.

위의 조건에서 생각해 볼 것!

냅색 알고리즘인가? - 하지만 가방이 여러개고 가방에는 보석을 하나만 넣는다.

그러므로 냅색 알고리즘 X

그러면 이제 생각해 볼것은 그리디 알고리즘이다.

음... 보니까 그리디 맞는 것 같다. 그러면 시간복잡도 계산부터 들어간다.

30만개의 보석과 30만개의 가방을 서로 각각 연결하면 900억번 계산한다.

그러므로! O(nlogn)의 방법을 써야 1억번(1초) 안으로 계산이 될 것 같다.

그럼 한 쪽을 log n으로 만들자. - 2가지 방법을 써봤다.

---

문제 풀어보기!!

첫 번째 - 실패:

가방 쪽을 logn으로 만들었다.

가방을 정렬하고 탐색할 때, 이분탐색으로 탐색하여 가방을 찾았다.

문제점: visit 배열을 만들어야 하고 최악의 경우 한번 visit 검사할 때 30만번이 계산된다.

즉, 시간은 줄더라도 logn이라고 볼 순 없다.

 

두 번째 - 성공:

보석 쪽을 logn으로 만들었다.

보석을 heapq에 가벼운 순으로 넣어버리고, 가방의 무게 제한까지 pop 시킨다.

pop 시킨 데이터는 새로운 heapq로 가격이 높은 순으로 넣어버리고

이제 이 heapq에서는 가방당 하나씩 뽑으면 된다.

** 가격이 높은 순의 heapq와 무게 가벼운 순의 heapq는 가방마다 없을 수도 있으므로, 있다는 것을 확인하기 위해 heapq의 데이터가 있는지 확인해야 한다. **

 

코드:

import heapq
from sys import stdin
input = stdin.readline

gems = []
N, K = map(int, input().split())
for i in range(N):
    w, c = map(int, input().split())
    heapq.heappush(gems, (w, c))

knapsack = [int(input()) for i in range(K)]
knapsack.sort()

res = 0
res_arr = []

for min_w in knapsack:
    while True:
        if gems and min_w >= gems[0][0]:
            w, c = heapq.heappop(gems)
            heapq.heappush(res_arr, -c)
        else:
            break
    if res_arr:
        res -= heapq.heappop(res_arr)

print(res)