[백준/python][DP] 12865번 - 평범한 배낭

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

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)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

---

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

코드

import sys
r_line = sys.stdin.readline
N, K = map(int, r_line().split())

arr = [(0,0)]
for i in range(N):
    arr.append(list(map(int, r_line().split())))

dp = [[0 for _ in range(K+1)] for _ in range(N+1)]

# 비즈니스 로직
for i in range(1, N+1):
    for j in range(1, K+1):
        weight = arr[i][0] 
        value = arr[i][1]
        
        if j < weight: 
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(value+dp[i-1][j-weight], dp[i-1][j])
            
print(dp[N][K])

 

풀이

정말 이해하기 힘들었던 문제.

 

이런 식으로 표가 나오며

첫 줄에 이미 0으로 전부 되어있는 배열이 이미 있기 때문에

if j < weight: 
            dp[i][j] = dp[i-1][j]

이 부분에서 인덱스 에러가 나지 않음.

 

알고리즘핵심은 항상 자신의 자리는 "현재까지의 물건 중 가장 가치 높은 구성"이다.

 

<제일 이해 안 됐던 부분 설명, 머릿속이 코딩적 사고로 이어지지 않았음(1시간 이상 소요) >

예를 들어,

가성비 좋은 물건(무게는 낮고 가치는 높은)
물건이 들어온다.

그리고 무게가 좀 더 높지만 가치가 더 낮은 물건이 전에 있었다면 

그 모든 자리를  가성비물건이 먹게 되기에 

어차피 자신의 자리는 "현재까지의 물건 중 가장 가치 높은 구성" 

 

그래서 7 무게를 구성하기 위해서 4의 무게가 들어올 때
7-4 = 3을 하여 3을 가져오는 이유는 어차피 1,2,3에서 3이 남은 무게 중 가질 수 있는 최대가치이기 때문이다.

=> 결론: 1,2,3이 있지만 3만 검사하면 되는 이유는 남은 것 중 최대가치는 가장 큰 게 되기 때문이다.

==> 부가설명) 3은 1,2를 전부 내포하고 있다.(무게가 높다는 건, 이 무게보다 낮은 것들이 들어왔었을 때 이미 시행착오를 겪은 거임)

 

그래서 

무게보다 커서 들어갈 수 없다면 

전에꺼를 넣고

무게가 되는 거라면 

합쳐서 무게가 되는 애(짝꿍)랑 더한다(내가 현재 구상할 수 있는 최대가치) <==>  전에 최대가치

를 비교하여 max값을 대입한다.

 

이렇게 되면 항상 그 무게의 위치는 물건이 늘어날 때마다 "현재구상되어 있는 물건 중 최대가치"가 되고

가치가 가장 높은 곳은 무게 상관없이 K의 위치가 가장 높다.

 

마지막 dp[N][K]가 정답이다.