[백준] 12865번 평범한 배낭

💡문제접근

• 냅색 알고리즘으로 유명한 문제다. 처음엔 가방의 무게를 기준으로 오름차순 정렬해서 접근했으나 WA를 받았다. 이런 식으로 접근하는 문제는 아닌 것 같았다.
• 2차원 배열을 이용해서 DP를 구현하는 문제였다. 표를 사용해서 나타내보면 다음과 같다.

💡테스트케이스

입력

4 7
6 13
4 8
3 6
5 12

출력

14

0	0	1	2	3	4	5	6	7
0, 0	0	0	0	0	0	0	0	0
6, 13	0	0	0	0	0	0	13	13
4, 8	0	0	0	0	8	8	13	13
3, 6	0	0	0	6	8	8	13	14
5, 12	0	0	0	6	8	12	13	14

• dp배열은 다음과 같이 정의할 수 있다.

dp[i][j] = 처음부터 i번째까지의 물건을 살펴보고 배낭의 용량이 j였을 때 배낭에 들어갈 수 있는 물건의 가치 합의 최댓값

• 냅색 알고리즘 문제는 쉽게 말해서, i번째 물건을 넣었을 때와 넣지 않았을 때를 비교하여 조건을 만족하면서 둘 중 가치가 더 높은 것을 가져오는 방식으로 진행하면 된다.
• 2차원 배열을 이용하는 방법에 익숙해지자

💡코드(메모리 : 229220KB, 시간 : 5584ms)

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split())
bag = [[0, 0]]
for i in range(N):
    w, v = map(int, input().strip().split())
    bag.append([w, v])

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

for i in range(1, N+1):
    for j in range(1, K+1):
        W = bag[i][0]
        V = bag[i][1]
        if j < W:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-W] + V)
print(dp[N][K])

💡소요시간 : 17m