[백준] 12865 평범한 배낭 python

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

12865번: 평범한 배낭

import sys; input = sys.stdin.readline
N, K = map(int, input().split())
stuff_list = [tuple(map(int, input().split())) for _ in range(N)]
memo = [[0 for _ in range(K + 1)] for _ in range(N + 1)]

for i in range(1, N + 1) :
    for j in range(1, K + 1):
        if stuff_list[i - 1][0] > j:
            memo[i][j] = memo[i - 1][j]
        else:
            memo[i][j] = max(memo[i - 1][j],
                             stuff_list[i - 1][1] + memo[i - 1][j - stuff_list[i - 1][0]])

print(memo[N][K])

Dynamic Programming 중 하나인 Knapsack 문제이다.

stuff_list은 인덱스마다 물건의 무게와 가치가 저장된 이차 배열이고, 메모이제이션을 사용하기 위해 (N + 1) * (K + 1)의 이차 배열을 선언하고 dp 방식으로 하나씩 채워가면된다. 

물건의 무게가 현재 찾는 무게보다 큰 경우 넣지 않는 것으로 판단하여 이전 값(i - 1)을 저장한다. 무게를 넘지않은 경우 넣지 않은 상태의 가치와 물건을 넣었을 때 만들수 있는 가치 중 최대값을 저장한다. 물건을 넣었을때 만들수 있는 가치는 물건의 가치에 이전 상태에서 물건만큼의 무게를뺀 값으로 구할수 있다. 

뭔가 말로하면 어려운데 `stuff_list[i - 1][1] + memo[i - 1][j - stuff_list[i - 1][0]]` 식으로 보면 조금더 쉽게 볼수 있다.