백준 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)

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

출력

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

 

해결방법

1. heapq(우선순위 queue)를 몰랐던 해결방안

시간복잡도 $N^2$ 임으로 시간초과로 풀지 못하였다. 해당 방법에 대해 서술하자면, 먼저 M_V( 무게 , 가격 ) 을 정렬 하는 방식을 취하였다.  첫번째 , 무게를 오름차순으로 정렬하고  둘째, 가격을 내림차순으로 정렬하여 진행하였으며 만약 가방과 보석이 선택된다면 list.pop()을 통해 삭제하는 방식을 취했다. 해당 알고리즘을 생각 한 이유는 높은 가격순으로 정렬하고  그 속에서 무게를 오름차순으로 정렬된다면 쉽게 분류할 수 있을 것이란 예상 때문이었다. 실제로 해당 방법은 옳았으나, if 문이 한번 더 존재한다는 점이 시간복잡도를 확연히 늘였다 (N^2)

(해당 방법)

N, K  = map(int,input().split())

M_V = []
for i in range(N):
    a =list(map(int, input().split()))
    M_V.append(a)

C = []
for i in range(K):
    C.append(int(input()))

C.sort()
M_V.sort(key=lambda x:x[0])
M_V.sort(key=lambda x:x[1],reverse=True)
cnt = 0
s = 0

while len(C) != 0:

    l = list(filter(lambda x: x[0] <= C[0], M_V))
    if len(l)==0:
        break
    s +=l[0][1]

    M_V.pop(M_V.index(l[0]))
    C.pop(0)

print(s)

(시간초과 코드)

 

해당 방법에서 나오는 시간복잡도를 해결하기 위해 heapq를 활용하였다. heap은 이진트리 구조를 통해 logN 의 시간복잡도를 제공한다. 따라서 N*logN + N 의 시간복잡도가 완성이 되어 결국 O(N)을 보장한다는 것이다.

import heapq

N, K  = map(int,input().split())

M_V = []
for i in range(N):
    a =list(map(int, input().split()))
    M_V.append(a)

C = []
for i in range(K):
    C.append(int(input()))

C.sort()
#M_V.sort(key=lambda x:x[0])
M_V.sort()
print(M_V)
cnt = 0
s = 0
j = 0
max_heap = []
for i in range(K):

    while j<N and C[i]>=M_V[j][0]:
        heapq.heappush(max_heap,-M_V[j][1])
        j+=1

    if len(max_heap)>0:
        b = heapq.heappop(max_heap)
        s+=abs(b)

print(s)

 

해당 방법에 대해 (Heap Q , priority Q ) 에 대해 조금 더 자세히 공부할 필요가 있다는 점을 인지하였다.

 

** while 문에 있는 조건문을 십분 활용 할 생각을 할 것 !! (조건문 여러개 넣기 )**