[백준/파이썬]12865번 - 평범핸 배낭 / 냅색, 다이나믹

---

접근 방법

 

대표적인 배낭 문제로 물품을 하나씩 선택하여 각 무게별로 어떤게 최고의 선택인지 갱신한다

---

풀이

 

이차원 배열을 선언하여 arr[선택한 물품][총 물품의 무게]로 만든다

물품1부터 하나씩 선택하며 각각의 무게가 최대일때

1. 이전물품까지의 가치를 그대로 가져올지

2. 이전물품까지에서 현재 물품의 무게를 뺀 가치에 현재 물품의 가치를 더한 값

둘중에 더 큰값을 저장하면 된다

 

따라서 점화식은 아래가 된다

w = arr[i][0]
v = arr[i][1]
bag[i][j] = max(bag[i-1][j], bag[i-1][j-w] + v)

---

정답 코드

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
arr = []
arr.append((0, 0))
for i in range(n):
  w, v = map(int, input().split())
  arr.append((w, v))

bag = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
  for j in range(1, k + 1):
    if j < arr[i][0]:
      bag[i][j] = bag[i - 1][j]
    else:
      bag[i][j] = max(bag[i - 1][j], bag[i - 1][j - arr[i][0]] + arr[i][1])

print(bag[n][k])

---

순서와 관계없이 더 최적의 경우를 구할 때 이차원 배열을 이용해서

각 상황에 맞는 답을 구해가는 점화식을 알아내는 것이 중요한 것 같다