💡문제접근
- 대학교 알고리즘 강의 때 들었던 내용이 기억나서 수월하게 접근할 수 있었다.
- 이 문제는 0-1 배낭 알고리즘에 관련된 동적 프로그래밍 문제로 모든 물건은 최대 한 개씩만 존재한다고 가정한다.
- 냅색 알고리즘과 관련된 동적 프로그래밍 문제를 좀 더 풀어봐야겠다.
- 뿐만 아니라 동적 프로그래밍 문제를 해결할 때 보통 시공간복잡도가 제약 조건이 까다롭지 않다면 2차원 배열을 통해서 해결하는데 이 문제는 2차원 배열을 사용하면 시간초과가 발생하므로 최대 힙을 통해서 문제를 해결하면 문제가 발생하지 않는다.
💡코드(메모리 : 87272KB, 시간 : 1604ms)
import heapq
import sys
input = sys.stdin.readline
N, K = map(int, input().strip().split())
arr = []
bag = []
for i in range(N):
M, V = map(int, input().strip().split())
heapq.heappush(arr, (M, V))
for j in range(K):
C = int(input())
bag.append(C)
# 배낭 역시 오름차순으로 정렬
bag.sort()
result = []
answer = 0
for Bag in bag:
# 배낭에 담을 수 있는 물건이 배낭의 무게보다 작거나 같으면?
# 배낭에 해당 물건을 넣는다.
while arr and Bag >= arr[0][0]:
heapq.heappush(result, -arr[0][1])
heapq.heappop(arr)
# 만약 최대 가치를 창출할 수 있도록 배낭에 물건을 넣었다면?
# 최대 가치를 계산한다.
if result:
answer -= heapq.heappop(result)
print(answer)💡소요시간 : 30m
🐢