백준 12865 - 평범한 배낭
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
여러 DP 문제들을 풀면서 여태껏 한 두 문제 빼고는 DP를 1차원 배열로 선언해서 풀었기 때문에 본능적으로 DP를 1차원으로 고정해버리는 못쓸 습관이 생겨버림..
이것도 문제랑 원리는 다 이해가 됐는데 구현해서 막혀버렸다..
DP에 소질이 없는걸로 쩝,,
이 문제는 여러 포스팅을 봐도 이해가 쉽지 않았다.
그 중에서 내가 이해하는데 도움을 받았던 포스팅은 이것이다.
코드리뷰를 해보며 나중에 시간이 지나 다시 볼 때도 이해가 가능하도록 자세하게 풀이해보고자 한다.
풀이코드)
n, k = list(map(int, input().split()))
bags = []
for i in range(n):
bags.append(list(map(int, input().split())))
dp = [[0]*(k+1) for i in range(n+1)]
for i in range(1, n+1):
for j in range(k+1):
w, v = bags[i-1]
if j >= w:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
else:
dp[i][j] = dp[i-1][j]
print(dp[n][k])
풀이에 적용한 알고리즘 흐름은 다음과 같다.
1. dp에 무엇을 저장해야하는가?
최종적으로 도출해야되는 결과값은, 모든 물건들을 고려했을 때 제한 무게 안에서의 최대 가치이다.
=> dp에는 i번째 물건까지 고려했을 때 제한무게가 j무게일 때의 최대 가치를 저장해야한다.
고려해본다는 뜻은 해당 물건을 담을지, 말지의 경우를 모두 따져본다는 것이지 반드시 넣는다는 아니다.
따라서, dp를 물건의 갯수 +1 만큼의 행을 만들고, 무게 +1 만큼의 열을 만들어 선언하였다.
이제 물건의 갯수만큼 반복문을 돌면서,
무게를 0부터 제한 무게까지 늘려가며 해당 무게에 올 수 있는 최대 가치를 저장하면 된다.
2. i 번째 물건을 고려할 때 올 수 있는 경우의 수는 다음과 같다.
2-1) 제한 무게 j 가 해당 i번째 물건 무게보다 작을 경우(제한 무게를 넘으면 안되니까)
=> i번째 물건을 넣을 수 X
==> 이전 물건까지 고려했을 때 해당 j무게까지의 최대가치 dp[i-1][j]
2-2) 제한 무게 j 가 해당 i번째 물건보다 클 경우
=> i번째 물건을 넣을 수 O
==> 넣을 것인지, 넣지 않을 것인지의 경우의 수를 고려
i번째 물건까지 고려했을 때 제한 무게 j의 최대가치: 넣었을 때와 넣지 않았을 때를 비교하여 더 최대값을 저장
2-2-1) 넣지 않았을 경우의 최대 가치
이전 물건까지 고려했을 때 해당 j무게의 최대가치
dp[i-1][j]
2-2-2) 넣었을 경우의 최대 가치
현재 무게 j가 넣었을 때의 무게가 되어야 하므로 무게가 j - 현재 물건의 무게에서의 최대가치를 가지고 계산해야한다.
해당 i번째의 무게를 w, 가치를 v라고 하면, dp[i][j-w] + v 가 해당 물건을 넣었을 때의 가치이다.
3. 2에서 고려한 경우의 수에서의 최대 가치를 dp에 저장-
==> max를 이용해서 계속 갱신해주면 된다.
위 알고리즘을 적용한 표(dp)는 다음과 같이 나온다.
