[백준] 12865번 평범한 배낭 - 파이썬(Python)

문제 (링크)

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

12865번: 평범한 배낭

 

나의 풀이

import sys
input = sys.stdin.readline

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

# dp[i][j] -> 최대 무게가 j일 때, i번째 물건까지 담을 경우 가질 수 있는 최대 가치
dp = [[0] * (k+1) for _ in range(n)]

for i in range(k+1):
    if items[0][0] <= i:
        dp[0][i] = items[0][1]


for i in range(1, n):
    for j in range(k+1):
        if items[i][0] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i][0]] + items[i][1])
        
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n-1][k])

 

코드 설명 및 풀이법

유명한 냅색 알고리즘 문제이다.

 

처음에는 백트래킹으로 접근하였으나, 시간초과 판정을 받아서 DP로 풀었다.

 

DP답게 점화식을 이해하는 것이 가장 중요한데, 이 문제는 지금까지 봐왔던 DP 테이블과는 다르게 2차원 배열을 사용했다.

 

dp[i][j]는 다음과 같이 정의될 수 있다.

 

"무게가 최대 j인 배낭에 i번째 물건까지 담았을 때 가질 수 있는 최대 가치"

 

이 값을 기록하기 위해서 i번째 물건이 배낭에 들어갈 수 있을 때, 두 가지 값을 비교해준다.

 

그 두 가지 값은 다음과 같다.

1) 무게가 j인 배낭에 i - 1번째 물건까지 들어갔을 때 최대 가치

2) 무게가 j인 배낭에 지금 넣으려는 i번째 물건의 무게만큼을 비우고, 현재 i번째 물건을 집어넣었을 때 가질 수 있는 가치

 

이 두 가지 값 중 최대값을 dp의 i열 j행에 기록해주면 최대값을 구할 수 있다.