1202:보석 도둑 [백준 문제풀이][Python]

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

난이도: 골드 2

학교에서 친구와 함께 푼 문제. 그리디 알고리즘을 쓰되, 최대한 효율적으로 최댓값을 구해야 한다.

아이디어1

우선 가방마다 담을 수 있는 무게가 다 다르기 때문에, 가방에 담을 수 있는 무게 C에 대하여 C보다 작은 보석 중 가장 가치 있는 보석을 계속해서 가져가면 된다.

실패한 이유

그러나 이 알고리즘은 잘못됐다. 왜냐하면 계산 과정이 매우 오래 걸리기 때문이다. 우선 C가 어디 사이에 있는 값인지 알아야 한다. 물론 bisect라는 이진탐색을 지원해주는 함수를 쓰면 되지만 그런다 하더라도, 최댓값이 어딨는지 찾는 과정에서 배열 순회를 해야하기 때문에 시간 초과가 날 것이다. 이를 해결해주기 위해서 전에 공부했던 우선 순위 큐를 사용해주면 된다! 

 

아이디어2

기본적인 아이디어는 max값을 찾는 과정을 우선순위 큐를 이용하여 시간복잡도를 O(logN)으로 줄여주는 것이다. bisect를 이용하여 들어갈 수 있는 보석들의 가치를 우선순위 큐에 넣어준다. 그리고 우선순위 큐에서 get()한 값을 sum에다가 더해준다. 그런 다음 bisect를 사용해 찾은 값부터 다시 탐색을 시작한다.(C는 정렬되있고, 그보다 가벼운 보석들은 이미 큐에 들어갔으므로 다시 넣어줄 필요가 없다)

이와 같은 과정을 거치면 된다.

정답 코드

import sys
input = sys.stdin.readline
from queue import PriorityQueue
import bisect
n,k = map(int,input().split())
w=[]#무게
j=[]#보석의 무게와 가치
for i in range(n):
    p,q = map(int,input().split())
    j.append((p,q))
j.sort()
for i in j:w.append(i[0])#무게만 따로 있는 리스트를 만들어준다.
b=[]
for i in range(k):
    b.append(int(input()))
b.sort()
s=0
sum=0
que = PriorityQueue()
for i in b:
    e=bisect.bisect_right(w,i)#마지막 위치 찾기
    for i in range(s,e):
        que.put(-j[i][1])#최댓값을 찾기 위해 음수 값으로 put()
    if(que.empty()):continue#만약 새로운 값이 없으면 continue
    sum+= -(que.get())#최대 가치 get()
    s=e#마지막 위치를 다시 시작 위치로
print(sum)