[백준 12865 골5] 평범한 배낭 (DP/python) -/3

https://www.acmicpc.net/problem/12865

내 코드

import sys
from collections import defaultdict

def make_dp():
    for key, value in values.items():
        for i in range(key, K+1):
            dp[i] = max(dp[i], dp[i-1], value+dp[i-key])

N, K = map(int, sys.stdin.readline().split())
values = defaultdict(int)
dp = [0 for _ in range(K+1)]
for _ in range(N):
    w, v = map(int, sys.stdin.readline().split())
    values[w] = v
make_dp()
print(dp)
print(dp[K])

당연히 틀렸다. 처음에 이걸 동전과 비슷한 사례로 볼 수 있을거라고 생각했는데 그게 아니었다. 반례는 다음과 같다.

1이 가장 가치가 높을 경우 1 짜리 짐을 무한히 담기 시작한다.

처음엔 큐를 써서 이미 담은 짐은 빼버릴까 했는데, dp와 큐를 같이 쓸 수 없었다.
dp(3) 에서는 1kg 짐을 담는 게 좋은 선택일 수 있으나, dp(4)에서는 1kg 짐을 빼는게 좋은 선택일 수도 있기 때문이다.

내가 짠 코드는 "무게가 늘어날수록" "짐의 가치도 높아질 경우에 한해" 올바르게 작동한다.

https://hongcoding.tistory.com/50 여기 제대로 된 설명이 있음