[백준] 12865번 : 평범한 배낭 (Python)

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

12865번: 평범한 배낭

문제

난이도 : GOLD V

입력 / 출력

전통적인 0-1 Knapsack 문제입니다.

오늘은 이 배낭문제를 완벽하게 파헤치겠습니다.

 

풀이 과정

DP 문제가 늘 그렇듯 DP값을 정의하는 것이 가장 중요합니다.

DP[N][K] = N번째 물건까지 담았을 때 용량이 K인 가방의 최대 가치

N번째 status는, N-1번째 status만 보고 도출할 수 있다는 것입니다. 그렇기 때문에, first case를 정의해주고, N번째 status와 N-1번째 status 사이의 관계만 정립해주면 이 문제는 쉽게 해결할 수 있습니다. 그렇기 때문에 DP인 것이죠.

 

소스 코드

import sys

input = sys.stdin.readline
N, K = map(int, input().split())
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
thing = [[-1, -1]]
for i in range(N):
	weight, value = map(int, input().split())
	thing.append([weight, value])

for i in range(1, N+1):
	for j in range(1, K+1):
		w = thing[i][0]
		v = thing[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])

 

메모리를 절약할 수 있을까?

PS를 할 때, 시간복잡도와 공간복잡도를 관리하는 것은 매우 중요합니다.

위에서 말했던 "N번째 status는, N-1번째 status만 보고 도출할 수 있다"라는 사실을 이용해 공간복잡도를 줄일 수 있었습니다. 항상 i번째와 i+1번째 상황만 보고 판단하기 때문에, 실질적으로는 일차원 배열 2개로도 충분히 풀어낼 수 있는 것이죠.

 

소스 코드(메모리 절약)

import sys

input = sys.stdin.readline

n, k = map(int, input().split())

a = [0 for _ in range(k+1)]
w, v = map(int ,input().split())
for i in range(w, k+1):
    a[i] = v
b = [0 for _ in range(k+1)]
for _ in range(n-1):
    w, v = map(int ,input().split())
    for i in range(min(w, k+1)):
        b[i] = a[i]
    for i in range(w, k+1):
        b[i] = max(a[i], a[i-w] + v)
    a = b
    b = [0 for _ in range(k+1)]
print(a[-1])

결과

메모리를 약 5.86배 절약할 수 있었습니다. 수행 시간도 줄어들었네요.