[백준] 12865번 평범한 배낭 (DP)
문제 출처
https://www.acmicpc.net/problem/12865
문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
풀이
유명한 냅색(KnapSack) 문제로 DP에 속한다.
DP는 Dynamic Programming으로 큰 문제를 작은 문제로 나눠푸는 알고리즘이다.
다음과 같은 input이 있을 때,
4 7
6 13
4 8
3 6
5 124개의 물품, 7의 무게를 의미하는 첫 행을 제외하면 다음과 같은 표로 변환할 수 있다.
다음 표가 의미하는 다음과 같다.
1. [6,13]행부터 K만큼 들었을 때 최대 가치를 의미한다. 첫 행에선 6 무게의 물품밖에 없기에 6과 7에 해당하는 최대 value는 13이다.
2. 그 아래 [4,8]의 물건이 추가가 되며 K=4~5일때는 4를 챙겼을 때의 무게인 8, K=6~7일때는 6의 물건을 챙겼을 때의 무게이다.
3. 그 아래 [3,6]의 물건까지 추가가 된다면 나머지는 이전과 동일하지만 K=7에서 13이 아닌 14가 된다. 이 부분이 가장 중요한데, 7(K)-3(W)에 해당하는 지점 + 6(New V)와 이전에 채워져있던 값 중 Maximum 값을 택한다.
(사실 맨 처음 생각했을때는 iteration을 돌며 확인하면 되는 것이 아닌가. 혹은 Brutal Force로 확인하면 되는 것이 아닌가 생각을 했었지만, 결국 어떤 한 물건을 기준으로 생각했을 때 최대 효용 case에 그 물건이 들어가거나 / 안 들어가거나 둘 중 하나다. 이 아이디어를 극대화 한 것 같다. 또한, 생각을 조금만 깊게 해보면 처음 주어진 Input의 순서는 상관 없다는 것을 알 수 있다.)
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
# 여기까진 input 대신 sys.stdin.readline 사용 (시간 초과 나지 않기 위해서)
bag = [list(map(int, input().split())) for _ in range(N)]
#가방에 [W,V]의 형태로 물건들을 담아준다
dp = [[0]*(K+1) for _ in range(N+1)]
#빈 N+1 by K+1 Matrix를 만들어준다.
for i in range(N+1): #물건을 하나 하나 돌며 확인
for j in range(K+1): #그럼 k value를 하나 하나 돌며 확인한다.
if j >= bag[i-1][0]: #만약 i번째 물건의 무게가 j(현재 가방에 넣을 무게)보다 작다면 ? 들어갈 가능성이 생긴다.
dp[i][j] = max(bag[i-1][1]+dp[i-1][j-bag[i-1][0]],dp[i-1][j]) #이때 이전의 최댓값과 현재 만들 수 있는 최대를 비교하여 더 큰 값으로 변경한다.
else: #나머지는 물건의 무게가 더 무거워 집어 넣지 못하는 경우이다.
dp[i][j] = dp[i-1][j] #이는 이전에 받은 최댓값을 그대로 받는다.
print(dp[N][K]) #그러면 이게 최대다.
한줄평 : dp는 참 끝이 없는 것 같다.