[snippet] knapsack.py

백준 12865번. 평범한 배낭에 대한 풀이를 0-1 Knapsack Problem의 스니펫 느낌으로 작성.

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

N, K = map(int, input().split())
arr = [(0, 0)] # 1-indexed
for _ in range(N):
    W, V = map(int, sys.stdin.readline().rstrip().split())
    arr.append((W, V))

#####################################
    
# y축: 몇번 물건(1~N)까지 고려했는지, x축: 현재 가방의 무게(1~K)
dp = [[0]*(K+1) for _ in range(N+1)] # 1-indexed, 2D

for i in range(1, N+1):
    w, v = arr[i]
    for j in range(1, K+1):
        if j-w < 0:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v) # i번 물건을 패스한다/넣는다

print(dp[N][K])

#####################################