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

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

 

해당 문제의 주어진 입력과 목표를 먼저 살펴봅시다.

 

 

1. 문제 입력 & 목표

해당 문제의 주어진 입력과 목표를 먼저 살펴봅시다.

 

문제 입력 

N: 물품의 수 (1 ≤ N ≤ 100)
K: 버틸 수 있는 최대 무게 (1 ≤ K ≤ 100,000)
w,v : 물건의 무게, 물건의 가치 (1 ≤ W ≤ 100,000 / 0 ≤ V ≤ 1,000)

 

 

문제 목표

배낭이 버틸 수 있는 최대 무게인 K가 넘지 않는 선에서, 담을 수 있는 물건의 최대 가치를 구해라

 

 

2. 접근 방식

문제의 첫 번째 예제를 시각화하면 다음과 같습니다. 

 

편의상 물건의 인덱스를 1부터 시작한다고 할 때,

왼쪽의 배열은 i번째 물건의 무게(w), 가치(v)이며, 오른쪽은 최대 배낭이 버틸 수 있는 무게인 7kg입니다.

 

이를 다음과 같이, 최대 i번째 물건, j무게까지 담을 수 있을 때의 최대 가치를 이차원 배열(arr)을 통해 표현해봅시다.

먼저, 첫 번째 물건만 담을 수 있다고 할 때 다음과 같이 값을 저장할 수 있습니다.

 

첫 번째 물건의 무게는 6kg로, arr[1][0]~arr[1][5] 는 물건을 담을 수 없어 최대가치가 0, arr[1][6]~arr[1][7] 부터는 물건을 담을 수 있으므로 첫 번째 물건의 가치인 13이 저장됩니다.

 

다음으로, 최대 두 번째 물건을 담을 수 있다고 했을 때는  arr[2][0]~arr[2][3] 까지는 0, arr[2][4] 부터는 두 번째 물건을 담을 수 있으므로 두 번째 물건의 가치인 8이 저장됩니다.

 

최대 6kg까지 배낭에 담을 수 있을 때는, 첫 번째 물건과 두 번째 물건 중 하나만을 선택해 담을 수 있으므로 두 물건의 가치를 비교해서 더 큰 가치를 가진 물건을 넣어주면 됩니다. 첫 번째 물건의 가치가 13으로 더 크므로, arr[2][6]~arr[2][7]는 13을 저장해줍니다.  

 

이와 같은 방식으로, 최대 세 번째 물건을 담을 수 있다고 했을 때, 다음과 같이 값을 저장할 수 있습니다.

 

하지만, 최대 7kg까지 담을 수 있을 때 최대 가치는 첫 번째 물건을 하나만 담는 것이 아닌, 두 번째 물건과 세 번째 물건을 함께 담았을 때 입니다. 이는 현재 담을 수 있는 최대 무게인 7에서 세 번째 물건의 무게인 3을 뺐을 때의 최대가치와 세 번째 물건의 가치를 더한 값으로 구할 수 있습니다.

 

네 번째 물건까지 담을 수 있을 때를 모두 계산한 결과는 다음과 같습니다. 

 

문제의 정답은 최대 네 번째 물건을 담을 수 있고 최대 7kg 무게까지 담을 수 있을 때의 최대 가치가 저장된 arr[4][7] 에 해당됩니다.

 

2.1) 2차원 DP로 풀어보기

위에서 전개한 내용을 2차원 DP로 풀어보도록 하겠습니다.

dp[i][j]에 저장되는 값은 최대 i번째 물건을 사용하여 최대 j무게까지 담을 수 있을 때의 최대 가치입니다.

wv = [(0,0)]
for i in range(1, N+1):
    w, v = map(int, input().split())
    wv.append((w,v))

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

for i in range(1, N+1):
    w, v = wv[i]
    for k in range(1, K+1):
        if k >= w: # 현재 무게가, k 보다 작거나 같을 때
            dp[i][k] = max(dp[i-1][k], dp[i][k-1], dp[i-1][k-w] + v)
        else: # 현재 무게가, k 보다 클 때
            dp[i][k] = max(dp[i-1][k], dp[i][k-1])

print(dp[N][K])

 

 

 

2.2) 1차원 DP로 풀어보기

위의 코드보다 더 적은 메모리, 시간을 사용하고 싶다면 1차원 DP로도 풀이가 가능합니다.

매 반복마다 tmp = dp.copy()를 해두어 이전 물건들 값의 최대가치를 참고할 수 있게 코드를 수정해줍니다. 

N, K = map(int, input().split())
wv = []
for _ in range(N):
    w, v = map(int, input().split())
    wv.append((w, v))

dp = [0] * (K+1)
ans = 0
for w, v in wv:
    tmp = dp.copy()
    for k in range(K+1):
        if dp[k] and k + w <= K and dp[k+w] < tmp[k] + v:
            dp[k+w] = tmp[k] + v
    if w <= K:
        dp[w] = max(dp[w], v)

print(max(dp))