[Python] 1202번 : 보석 도둑

문제 3줄 요약

1. 상덕이는 도둑이다.

2. 보석은 총 N개, 무게는 M, 가격은 V

3. 상덕이 가방 개수 K개, 담을 수 있는 무게는 C이며 가방 당 최대 한 개, 최대 얼마까지 훔칠 수 있을까?

 

 

문제를 읽고

직관적으로 느낀 해결법은

가방에 담을 수 있는 최대 무게가 작은 가방부터

무게 당 가격이 높은 보석을 넣어야한다는 것이었다.

 

따라서 무게 당 가격이 높은 보석 순으로 정렬하고

차례대로 가방에 넣고 해당 보석은 제외시키는 방법을 하니

바로 시간 초과 ㅎ..

 

아무래도 리스트에서 값을 지우는 것은

리스트를 한바퀴 돌아야하므로 효율적이지 못했던 것 같다.

그리고 한번 거쳤던 보석들도 다시 재비교 한다는 것을 알 수 있었다.

 

 

Ex) 무게가 1, 2, 3 가격이 5,6,7인 보석이 있다.

 

가방이 1,2,3의 크기라면,

1인 가방에서는 첫 번째 보석을 넣고 가치는 +5를 할 것이다.

그럼 그 다음 2인 가방에서는 보석 1을 다시 비교해야한다.

 

때문에 비교하는 횟수를 줄이기 위해

한번 거쳤던 보석들은 heapq에 내림차순으로 담아

재비교를 피해주었다.

 

 

from sys import stdin
import heapq

if __name__ == "__main__":
	# 보석, 가방의 수
    N,K = map(int, stdin.readline().split())
    answer = 0
    
    # 무게와 가치를 담는 리스트
    mv_list = []
    for _ in range(N):
        M,V = map(int, stdin.readline().split())
        mv_list.append([M,V])
    
    # 가방을 크기 오름차순으로 넣기
    c_queue = []
    for _ in range(K):
        heapq.heappush(c_queue, int(stdin.readline()))

	# 보석 무게 순으로 정렬
    mv_list = sorted(mv_list, key=lambda item : item[0])

    idx = 0
    item_queue = []
    while(len(c_queue) != 0):
        C = heapq.heappop(c_queue)
        # 가방에 들어갈 무게인 보석을 가치 내림차순으로 넣기
        while(idx < N and C >= mv_list[idx][0]):
            heapq.heappush(item_queue, -mv_list[idx][1])
            idx += 1
        # 가장 가치가 높은 보석 빼기
        if item_queue:
            answer += -heapq.heappop(item_queue)
    print(answer)

 

재비교를 하지 않고 가치가 높은 보석을 빼는 방법이

쉽지 않았다..

저 짧은 5문장이 어마어마한 일을 한다 ㅎ..

 

끝!