[백준 12865번] 평범한 배낭

난이도: 골드 5

문제 링크: www.acmicpc.net/problem/12865

12865번: 평범한 배낭

문제 12865번: 평범한 배낭

오늘 공부한 다이나믹 프로그래밍을 응용해 보기 위해 풀어 본 문제입니다.

얼핏 보면 간단해 보이지만, 두 개의 변수 W와 V를 고려해야 해서 쉽지 않습니다.

제가 예전에 풀었던 최소 편집 거리 문제와 비슷하다는 느낌을 받았습니다.

나름 유명한 문제인데, Google 등에 knapsack 문제라고 검색해 보시면 이 문제가 나옵니다.

 

먼저, 문제에서 주어진 조건을 확인해 봅시다.

제한 시간은 2초, 메모리 제한은 512MB로, 메모리와 시간 모두 꽤 넉넉한 편입니다.

주어진 변수는 총 네 종류, 물품의 수 N: 1 ≤ N ≤ 100; 버틸 수 있는 무게 1 ≤ K ≤ 100,000; 물건의 무게 1 ≤ W ≤ 100,000; 물건의 가치 0 ≤ V ≤ 1,000 가 있습니다.

N과 K가 최대값을 가진다면, 100개의 물건에 대하여 무게와 가치를 각각 비교해 봐야 합니다.

이를 그리디 메소드로 접근한다면 제한 시간 내에 풀 수 없을 것입니다.

 

따라서 이 문제는 다이나믹 프로그래밍, 그 중에서도 바텀-업 방식을 이용하여 접근해 봅니다.

그러기 위해서는 dp 테이블이 필요한데, 물건의 개수 N x 전체 무게 K의 이차원 배열을 dp 테이블로 활용합니다.

 

다음 예제를 가지고 풀이를 접근해 보겠습니다:

4 7

6 13

4 8

3 6

5 12

 

N = 4, K = 7이며, 그 아래로는 각 물건의 무게와 가치가 주어집니다.N = i, K = j로 둡니다.

각 i에 대하여, 해당하는 무게 W와 가치 V를 각각 weight, value 라는 변수에 담습니다.

 

그러면 크게 두 가지 경우가 생깁니다.

각 무게 j에 대해서, i번째 물건의 무게를 고려했을 때 담을 수 있는지 없는지 판단하게 됩니다. 이는 j < weight 로 판별합니다.

물건을 담을 수 없는 경우, 가방에 담긴 무게와 가치는 이전과 같게 됩니다. 따라서, dp[i][j] = dp[i-1][j] 입니다.

무게 j는 이전과 같으므로 변함이 없고, 물건 i는 이전과 같으므로 i-1을 통해 이전 물건을 가리키게 됩니다.

 

다음으로, 물건을 담을 수 있는 경우에 대해 생각해 봅시다.

여기서도 또 두 가지 경우로 나뉘는데요.

물건을 담을 수 있으니 담는 경우와, 물건을 담을 수 있지만 담지 않는 경우가 있습니다.

물건을 담는 경우는, 새로운 물건을 담으므로, 이전의 상태에서 무게를 빼고 (남은 가능한 무게 = 현재 무게 - 추가되는 무게), 가치를 더합니다.

이를 식으로 나타내면, dp[i][j] = dp[i-1][j] - dp[i-1][j-weight] + value 가 됩니다.

수식이 이해가 되시나요? 가만히 생각해 보시면 이해가 되지만, 백지 상태에서 이를 떠올리기란 쉽지 않을 것입니다.

이번 가방의 상태 = dp[i][j], 이전 가방의 상태 = dp[i-1][j], 새 물건의 무게를 뺐을 때의 가방이 가지는 가치 = dp[i-1][j-weight], 새 물건의 가치 value 가 됩니다.

다음으로, 담을 수 있지만 담지 않는 경우는, 앞서 경우와 마찬가지로 dp[i][j] = dp[i-1][j] 가 됩니다.

우리가 찾고자 하는 결과는 물건들의 무게를 만족하면서 가치가 최대가 되는 경우입니다. 따라서, 두 경우 중 얻게 되는 값이 더 큰 경우를 선택하면 됩니다.

dp[i][j] = max(dp[i-1][j] - dp[i-1][j-weight] + value, dp[i-1][j])

다시 위 예로 돌아가서, dp테이블을 그려 봅시다.

 

위 예시를 기반으로 그린 dp 테이블

i는 물건의 번호입니다. i = 1일 때는 첫 번째 물건 (무게 6, 가치 13) 만을 고려하며, i = 2일 때는 앞선 물건에 더해 두 번째 물건 (무게 4, 가치 8) 을 고려합니다. i = 4일 때는, 물건 전체를 고려하는 것이 됩니다.

j는 현재 고려하고 있는 가방의 최대 용량입니다. j = 7일 때는, 주어진 조건에 걸맞는 가방 용량까지 고려한 것이 됩니다.

구조를 보면 아시듯, 다음 dp[i][j] 를 구하기 위해 이전에 계산한 dp 테이블의 값을 가져다 사용합니다.

dp[4][7] = 14 가 가방에 넣을 수 있는 물건들의 값의 최대치가 됩니다.

 

위 코드를 수행하면 다음과 같은 결과를 얻음을 확인할 수 있습니다.

 

실행 결과

위에는 dp 테이블을 출력하였고, 맨 아랫줄에는 문제에서 요구하는 값을 출력하였습니다.