[BOJ, Python] 12865번_평범한 배낭

백준 12865번

요즘 하나 고쳐야할 습관이 있다.
가장 많이 사용하고, 익숙한 알고리즘은 그래프 탐색(Bfs, Dfs)여서 그런지 조금 유사한 문제를 만나면 우선 그래프 탐색으로 풀 방법을 궁리하게 된다.

해당 문제는 그래프 탐색이 아닌 다이나믹 프로그래밍의 대표적인 문제이다.

문제를 푸는 방법은 간단하다. 각 물건에 대해서 배낭의 용량을 1에서 최대치인 k까지 1씩 올려가면서 최대값을 찾으면 된다.

코드를 보자

전체 풀이

import sys
input = lambda: sys.stdin.readline().rstrip()

def Dynamic(weights, values, k):
    n = len(weights)
    dp = [[0]*(k+1) for _ in range(n+1)] # dp[i][w]: 첫번째 물품부터 i번째 물품까지 고려하고, 배낭의 용량이 w일때 최대 가치

    for i in range(1, n+1):
        for w in range(1, k+1):
            if weights[i-1]<=w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
            else: 
                dp[i][w] = dp[i-1][w]
    return dp[n][k]


N, K = map(int, input().split()) # 물품의 수, 버틸 수 있는 무게

w = []
v = []
for _ in range(N):
    W,V = map(int, input().split()) # 물품 무게, 물품 가치
    w.append(W)
    v.append(V)
print(Dynamic(w,v,K))

코드를 보면 dp를 이중 리스트로 생성한 것을 볼 수 있다.

dp = [[0]*(k+1) for _ in range(n+1)]

위에서 설명했듯이 각 물건에 대해서 배낭의 용량을 1씩 올려가며 최댓값을 찾기 위해서 이다.
dp[i][w]는 첫번째 물품부터 i번째 물품까지 고려하고, 배낭의 용량이 w일때 최대 가치를 뜻한다.

for i in range(1, n+1):
        for w in range(1, k+1):
            if weights[i-1]<=w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
            else: 
                dp[i][w] = dp[i-1][w]
    return dp[n][k]

해당 코드를 보면 이중 반복문이 사용되고, 조건문으로 if weights[i-1]<=w: 해당 물품의 무게(weights[i-1])가 배낭의 무게(w)보다 작을 시 dp[i][w]는 물품을 추가하지 않은 경우의 가치와 물품을 1개 추가했을 때의 가치를 비교해서 큰 값이 된다.

이중 반복문을 다 돌면
dp[n][k]는 첫번째 물품부터 n번째 물품까지 고려하고, 배낭의 용량이 w일때의 최대 가치를 뜻한다. 즉, 우리가 구해야 할 답이 된다.

결과