[백준/골드2] [1202] 보석도둑 - python, Pypy 3

부등호

문제내용 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 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.jewels와 bags 정렬하기

2. bags를 for문을 돌면서 가방의 무게보다 작거나 같은 보석에서 최대 가치 보석 찾기

  2-1 가방의 무게보다 작거나 같은 보석은 heap list에 넣고 heap list에 넣은 보석은 jewels에서 pop 해준다.

  2-2 만약 heap list에 원소가 하나라도 있으면 heappop을 이용해 가장 큰 가치를 가지 보석을 pop 해준다.

 

- 2-1 에서 jewels 리스트가 이전에 정렬이 되어 있기 때문에 heappop을 사용하면 인덱스 0번쨰 가장 작은 원소를 반환시켜준다.

- 2-2 heap list를 쓰기 때문에 매번 가방을 찾을 때마다 모든 보석을 탐색하지 않아도 heap list에 가장 가치가 높은순으로 정렬이 되어 있어 적은 시간 안에 찾는 것이 가능하다.

- heap 리스트에 넣고 뺄 때 (-1) 곱하기를 해주는 이유는 heap list는 최소 힙으로 구성이 되어있기 때문에 현재 코드에서 필요한 것은 최대 힙이기 때문이다. 

  - (-)만 붙일 수 있지만 (-1) 곱하기를 사용해준 이유는 가끔 (-)만 붙였을 때 제대로 실행되지 않는 것을 경험한 적이 있기 때문이다... 

---

전체코딩

 

- 코드

import heapq
import sys
 
#입력
N, K = map(int, sys.stdin.readline().split())
jewels = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
bags = [int(sys.stdin.readline()) for _ in range(K)]
 
# 정렬
jewels.sort()
bags.sort()
 
# 가방의 무게보다 작거나 같은 보석에서 최대 가치인 보석 찾기
answer = 0
data = []
for b in bags:
    while jewels and b >= jewels[0][0]:
        heapq.heappush(data, (-1)*jewels[0][1])
        heapq.heappop(jewels)
                
    if data: # 가방에 넣을 수 있는 보석이 있는 경우
        answer += (-1) * heapq.heappop(data)
        
# 출력
print(answer)

 

 

 

---

시간 초과가 날 때는 pypy3와 입력을 import sys로 바꾸어만 주어도 시간 초과가 해결될 때가 있는데 이번에는 변경해도 해결되지 않아 생각보다 많은 시간을 소요했던 것 같다

처음에 이중 for문으로 코드를 짰다가 그렇게 되며 너무 많은 시간을 소요하게 된다는 것을 알고 이렇게 다시 코드를 짜게 되었다