[BOJ] 12865 평범한 배낭

👉 들어가기

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

직전에 풀었던 동전 1 문제와 거의 비슷한 개념으로 풀 수 있는 문제입니다!
마찬가지로 DP 문제이며 동전 문제와 차이점이 있다면, 동전 문제는 값을 누적해야 하는 문제였지만
평범한 배낭 문제는 값을 저장해놓고 최대가 되는 값을 계속 비교해야 합니다.

✏️ 문제 풀이

from sys import stdin
input = stdin.readline

n, k = map(int, input().split())
item = [[0, 0]]
for i in range(1, n+1):
    item.append(list(map(int, input().split())))

dp = [[0]*(k+1) for _ in range(n+1)]  # (n+1) x (k+1) 형태의 2차원 배열

for i in range(1, n+1):
    for j in range(1, k+1):
        if j >= item[i][0]: # k 값보다 작을 경우 item을 더하는 경우를 고려한다.
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][k])

개념은 이전 문제와 비슷하니, 이번엔 코드를 보면서 설명하겠습니다.
n은 물건의 갯수, k는 배낭이 견딜 수 있는 최대 무게를 의미합니다.
item 배열엔 [[0,0], [6,13], [4,8], [3,6], [5,12]] 의 [무게, 가치] 를 담은 배열로 저장합니다. (풀이에선 인덱싱을 위해 [0, 0]을 추가하였습니다)

[6, 3]을 이용한 경우

무게	1	2	3	4	5	6	7
6	0	0	0	0	0	13	13
4
3
5

먼저 item 중 [6, 3]을 이용하여 최대 가치인 dp[k] 를 구해보겠습니다.

6을 이용해선 dp[1]을 구할 수 없습니다. 따라서 dp[1] = 0 입니다.
6을 이용해선 dp[2]를 구할 수 없습니다. 따라서 dp[2] = 0 입니다.
...
6을 이용해 dp[6]을 구합니다. dp[6] = 13 입니다.
6을 이용해 dp[7]을 구합니다. dp[7] = 13 입니다.

이때, dp[7] 에서의 7은 가능한 최대한의 무게이므로, 더 작게 들어가도 괜찮은 값이고 아직은 6으로만 채워야 하므로 dp[7] = 13 입니다.

[4, 8]을 추가로 이용한 경우

무게	1	2	3	4	5	6	7
6	0	0	0	0	0	13	13
4	0	0	0	8	8	13	13
3
5

...
4를 이용해 dp[5]을 구합니다. dp[5] = 8 입니다. (위의 dp[7]을 구할 때와 같은 방식)
4를 이용해 dp[6]을 구합니다. dp[6] = 13 입니다.

여기서 이제 동전 문제와 다르게 이전의 값을 기억했다가 비교해야 합니다.
사실 6에서 저장한 dp[6]은, dp[6][1] 입니다.

반면, 현재 [4,8] 에서 말하는 dp[6]은 인덱스는 dp[6][2] 입니다!
이전의 dp[6][2-1]과 dp[6][2] 를 비교하여 더 큰 값을 선택하게 됩니다.(max(dp[6][i-1], dp[6][i]))
따라서 dp[6][2] = 13이 되겠습니다.

[3, 6]을 추가로 이용한 경우

무게	1	2	3	4	5	6	7
6	0	0	0	0	0	13	13
4	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
5

...
이제 이 문제의 정답이 나오는 부분이고 여기서 점화식을 완성할 수 있습니다.

3을 이용해 dp[7]을 구합니다. 먼저 dp[7][3] 은, 7 - item[3][0] = 4 이므로 바로 이전 행에서 제일 큰 값이었던 dp[4][2] 에 현재의 무게인 item[3][1]을 더한 14가 됩니다!

따라서, 위의 점화식에 따라 max(dp[7][2], dp[7][3]) = 14 이므로 최종적으로 14가 됩니다.

최종적으로 점화식을 정리하면 다음과 같은 형태를 띄게 되겠습니다.
dp[n][k] = max(dp[n-1][k], dp[n-1][k-item[n][0]] + item[0][1])

🙋🏻‍♀️ 유사한 문제

담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)
담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)

위의 문제는 0-1 Knapsack problem에 해당합니다.

감사합니다 :)