백준 GOLD 5 [12865번] 평범한 배낭 {언어 : Python} [다시 풀어 보기]

문제 링크

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

정답 코드

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
dp = [[0] * (k+1) for _ in range(n+1)]
for i in range(1, n+1):
    w, v = map(int, input().split())
    for j in range(1, k+1):
        if j >= w:
            dp[i][j] = max(v+dp[i-1][j-w], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][k])

풀이 방법

• DP 배열의 의미:
  dp[i][j]dp[i][j]dp[i][j]는 앞에서 iii번째 물건까지 고려했을 때, 배낭의 최대 무게가 jjj일 때의 최대 가치를 저장.

느낀점

• 오랜만에 dp를 푸는데 어려웠다.
• dp일 거라고 추측은 했지만 방법을 잘 몰랐다.
• dp가 2차원 배열로도 만들 수 있다는 부분을 간과했다.