처음에 시도하려 했던 방법(실패)
- 보석들을 Tuple pair로 이루어진 List를 만든다. ([(1, 65), (5, 23), (2, 99)])
- 보석의 무게가 높은 순으로 정렬 ([(2, 99), (1, 65), (5, 23)])
- 가방 무게가 큰 순으로 정렬 ([10, 2])
- 가방에 들어갈 수 있는 보석 무게를 무거운 순으로 넣고 List에서 제거
=> 시간초과
우선순위 큐로 문제를 풀어야했다.
코드
import sys
import heapq
N, B = map(int, sys.stdin.readline().split())
heap = []
for i in range(N):
heapq.heappush(heap, list(map(int, sys.stdin.readline().split())))
B_list = [int(sys.stdin.readline()) for i in range(B)]
B_list.sort()
res = 0
tmp_heap = []
# 적게 나가는 가방 무게부터 탐색
for B_weight in B_list:
# 아직 넣지 못한 보석이 있고, 가방 무게보다 작거나 같은 보석이라면(최소힙)
while heap and B_weight >= heap[0][0]:
heapq.heappush(tmp_heap, -heapq.heappop(heap)[1])
if tmp_heap:
# 기본적으로 최소힙으로 작동하기 때문에 21번째 줄에 -를 붙임(최대힙)
res += -heapq.heappop(tmp_heap)
print(res)
입력값 예시
보석 : [(1, 65), (2, 99), (5, 80)]
가방 : [10, 2]
<가방의 무게가 큰 순서대로 보석을 넣을 경우>
가방 무게 : 10 -> 들어간 가격 : (2, 99)
가방 무게 : 2 -> 들어간 가격 : (1, 65)
총 보석값 : 164
<가방의 무게가 작은 순서대로 보석을 넣을 경우>
가방 무게 : 2 -> 들어간 가격 : (2, 99)
가방 무게 : 10 -> 들어간 가격 : (5, 80)
총 보석값 : 179
가방의 무게에 따라 보석값이 달라지므로 가방의 무게가 작은 순서대로 넣어야한다.
보석 무게 : 최소힙
보석 값 : 최대힙
최대힙과 최소힙을 사용해야한다.
'코딩테스트 > Python' 카테고리의 다른 글
[python 백준 5052] 전화번호 목록 (0) | 2023.01.16 |
---|---|
[python 백준 13904] 과제 (0) | 2023.01.15 |
[python 백준 1931] 회의실 배정 (1) | 2023.01.14 |
[python 백준 1946] 신입 사원 (0) | 2023.01.13 |
[python 백준 6068] 시간 관리하기 (1) | 2023.01.09 |