백준 12865번 평범한 배낭 파이썬

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

12865번: 평범한 배낭

 

 

내 답안

import sys

input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
dp = [0] * (K + 1)
for _ in range(N):
    W, V = map(int, input().rstrip().split())
    for i in range(K, W - 1, -1):
        dp[i] = max(dp[i], dp[i - W] + V)
print(dp[K])

---

 

여기서 의문점이 생길 수 있다.

V, W = map(int, input().rstrip().split())
    for i in range(K, W - 1, -1):
        dp[i] = max(dp[i], dp[i - W] + V)

" 왜 for 을 0부터 돌리지 않고 K 부터 돌릴까? "

이유는 바로 물건의 중복을 피해서 메모이제이션을 하기 위해서 이다.

for문을 0부터 돌린다면 물건 하나가 중복해서 여러번 기록이 될수있다.

 

< 예시 >

입력이

3 5
4 2
3 4
1 5

라고 예를 들어보자.

정답대로 dp를 설계하면

dp = [0, 5, 5, 5, 9, 9] 가 나오게 된다. 따라서 답은 9가 된다. 

하지만 앞에서부터 순차적으로 메모이제이션을 한다면 중복을 포함하기 때문에

dp = [0, 5, 10 ,15, 20, 25] 가 이렇게 나오고, 틀린 정답 25가 출력되게 된다.

이 부분을 주의하면 실수하지 않고 배낭 문제를 쉽게 해결할 수 있다.