https://www.acmicpc.net/problem/1202
공부 날짜 : 2022.11.16
정답 참조 여부 : O
보석 n개가 각각 다른 무게와 가치를 가진다. k개의 가방이 있고 각 가방에 담을 수 있는 무게가 다를 때 가방에 담을 수 있는 최대 가치를 구하는 문제이다.
알고리즘은 어렵지 않았지만, 자료구조를 몰라서 정답을 참조한 문제
내가 떠올린 방법은 이렇다.
- 가방에 담을수 있는 무게가 작은 것부터 담기 시작한다.
- 현재 가방에 담을 수 있는 보석중에서 가장 가치있는 보석을 담는다
- 반복한다.
이렇게 생각했는데 아무리 해도 시간초과가 나왔고 시간을 줄이기 위해 여러가지 생각해봤지만 도저히 모르겠어서 정답을 참고 했다.
정답에서는 방법은 같지만 보석들의 저장을 heap구조를 사용한게 틀렸다.
나는 2번 과정을 모든 보석들에 대해서 살펴봤는데 힙구조를 사용해서
담을 수 있는 보석을 가치가 높은 heap구조로 저장해서 그중에서 최대 가치인 보석만 추가하는 방식이었다.
즉 보석을 입력받을때 무게를 기준으로 최소힙 정렬을 하고
현재 가방에 담을수 있는 보석을 pop해서 가치를 기준으로 최대힙정렬해서 저장했다.
현재 가방에서는 가치를 기준으로 최대힙정렬된 배열에서 heappop만 해주면 되는 방식이었다.
코딩을 할줄만 알고 아직 컴퓨터 지식이나 자료구조 등에 많이 부족함을 알고 왜 자료구조 지식이 필요한지 알 수 있었던 문제였다.
이 문제를 계기로 heap구조에대해서 어느정도 이해 할 수 있었고, 앞으로 공부할게 늘어서 오히려 설레고 있다.
소스코드
import sys
import heapq
input = sys.stdin.readline
####################################################
n, k = map(int, input().split())
jam = []
for _ in range(n):
heapq.heappush(jam, list(map(int, input().split())))
bag = []
for _ in range(k):
bag.append(int(input()))
bag.sort()
####################################################
result = 0
can_input_jam = []
for max_m in bag:
for _ in jam:
if jam[0][0] > max_m:
break
heapq.heappush(can_input_jam, -heapq.heappop(jam)[1])
if can_input_jam:
result -= heapq.heappop(can_input_jam)
elif not jam:
break
print(result)
