백준 12865번: 평범한 배낭 [골드 5] - Python

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

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

출력

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

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

 

풀이

문제를 풀고 알았지만 이 문제는 배낭 문제(Knapsack Problem)라는 유명한 문제였습니다. 배낭에 넣을 수 있는 물건의 양이 한정되어 있을 때, 최대의 가치로 넣는 방법은 무엇인가를 구하는 문제죠! 참고로 분할 가능한 배낭 문제와 분할 불가능한 배낭 문제 두 가지가 존재합니다만, 분할 가능한 문제는 그리디 알고리즘으로도 풀 수 있는 매우 쉬운 문제입니다.

만약 배낭에 넣을 물건들이 물이나 설탕처럼 나누어서 넣는 것이 가능하다면, 그냥 가치가 가장 높은 물건을 배낭에 넣을 수 있을 만큼 넣고, 그다음으로 가치가 높은 물건을 빈 자리에 넣을 수 있을 만큼 넣고.. 이러다가 꽉 차면 멈추면 됩니다. 이것이 분할 가능한 배낭 문제 입니다.

 

하지만 물건을 나눌 수 없다면 문제가 어려워지죠.. ㅠ 단순히 가치가 가장 높은 물건을 넣을 수가 없습니다. 가치가 더 낮은 물건 여러 개를 넣는 것이 총합의 가치가 더 높을 수도 있기 때문입니다. 이것이 분할 불가능한 배낭 문제 입니다.

 

분할 불가능한 배낭 문제는 다이나믹 프로그래밍으로 풀어야 합니다. 먼저 DP테이블을 만듭니다. DP테이블은 특정 무게의 짐이 가질 수 있는 최대 가치를 저장해 둘 것입니다. 배낭에 들어가는 최대 무게가 k이므로, DP테이블은 크기가 k+1(왜냐하면 0~k를 저장해야 하니까!)인 리스트로 정의합니다. 처음에는 모든 값을 0으로 초기화 합니다.

 

그리고 물건을 위에서부터 차례대로 배낭에 넣어보면서 DP테이블을 갱신합니다. 갱신하는 방법은 다음과 같습니다.

 

배낭에서 물건을 넣을 수 있는 무게를 확보한 후에 물건을 넣었을 때의 가치와 무게를 확보하기 전 가치를 비교해 더 큰 값으로 DP테이블을 갱신한다. 

 

무슨 말이냐고요? 예를 들어 이번 물체의 무게가 5, 가치가 7이라고 합시다. 그럼 이 물건을 넣을 때에는 dp[5]와 dp[0]+7을 비교해 더 큰 값을 dp[5]에 넣는다는 말입니다. 왜냐?! dp[5]는 이번 물건을 고려하지 않았을 때, 무게 5의 최대 가치입니다. 그런데 이번 물건을 고려하게 된다면, 먼저 이번 물건을 넣기 위해 무게 5를 확보해야 합니다. 무게 5를 확보한 상태라면 dp[0]이죠. 그리고 이번 물건을 넣지 않고 최대인 무게(dp[5])와 이번 물건을 넣었을 때의 최대 무게(dp[0]+7)을 비교해 더 큰 값이 이번 물건을 고려했을 때의 최대 가치가 되는 것입니다.

 

그리고 이 갱신을 DP테이블의 마지막 인덱스까지 해야 합니다. 즉 그 다음은 dp[6]과 dp[1]+7을 비교하고, 그 다음은 dp[7]과 dp[2]+7을 비교하고.. 이를 반복하는 거죠!

 

하지만 이 설명은 사실 틀렸습니다. 중요한 점 하나를 빠트렸기 때문인데요, 바로 이 작업은 역순으로 해야 한다는 점입니다. 그러니까 사실 dp[5]를 갱신한 후 dp[6]을 갱신하고, dp[7]을 갱신하고.. 가 아니라 dp[k]를 갱신하고 dp[k-1]을 갱신하고.. 마지막으로 dp[5]를 갱신해야 한다는 것입니다.

 

왜일까요? 만약 dp[5]부터 갱신하기 시작해서 dp[5]가 dp[0]+3으로 변했다고 합시다. 그런데 dp[10]을 갱신할 때에는 어떨까요? dp[10]은 dp[10] vs dp[5]+3이 될 것입니다. 그런데 이러면 어떻죠? dp[5]가 이미 dp[0]+3으로 변해버렸습니다.. 이러면 제대로 된 갱신이 불가능해집니다. 그래서 앞의 DP가 변하지 않게 하기 위해서 역순을 해야 하는 것입니다.

 

이를 구현한 코드입니다.

 

정답 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
stuffs = [list(map(int, input().split())) for _ in range(n)]

dp = [0]*(k+1)
for stuff in stuffs:
    w, v = stuff[0], stuff[1]
    for i in range(k, w-1, -1):
        dp[i] = max(dp[i], dp[i-w]+v)

print(dp[-1])

 

쉽지 않은 문제였음에도 불구하고, 코드의 길이는 꽤나 짧습니다. 그래서 사실 풀고나면 그렇게 어렵지 않다고 생각이 들기도 합니다.

 

어렵게 느껴지는 이유

사실 풀고나니 평범한 DP문제라고도 생각이 드는데, 많은 분들이 이 문제를 어려워하시고 해설을 읽어도 이해가 잘 되지 않는다고 말씀하시는 것 같습니다. 사실 저도 그랬어요 ㅋㅋㅋ.. 왜일까요? 그래서 제 나름대로의 이유를 생각해 봤습니다.

 

그 이유는 아마 이 문제가 전형적인 DP 문제가 아니라서가 아닐까 생각합니다. 이 문제는 일단 바텀업 혹은 탑다운으로 풀리지 않습니다. DP테이블을 아래에서부터 채워 올라가거나 위에서부터 채워 내려가는 방식이 아니죠. 어느 부분이 먼저 갱신될 지 알 수가 없습니다. 또 일반적으로 무게가 5인 물건을 배낭에 넣는다면, dp[5]만 갱신될 것으로 생각이 되지, dp[5] ~ dp[k]까지 갱신될 거라고 잘 생각을 못 합니다. 그래서 저도 먼저 물건의 무게를 오름차순으로 정렬한 후 바텀업으로 해결하려다가 실패했습니다. 애초에 DP테이블의 갱신 방식이 전형적인 DP문제와는 달랐기 때문이죠.

그렇기 때문에 다이나믹 프로그래밍 문제는 꼭 바텀업 혹은 탑다운만 있는 것이 아니다! 라는 것을 유념하고, 유연한 사고를 통해 문제를 해결해야 할 것 같습니다!