BOJ - 12865 - 평범한 배낭

Updated:

import sys

def solution():
    N, K = map(int, sys.stdin.readline().split())
    dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
    item = [[0, 0]]

    for _ in range(N):
        V, W = map(int, sys.stdin.readline().split())
        item.append([V, W])

    for i in range(1, N+1):
        for j in range(1, K+1):
            if j >= item[i][0]:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[-1][-1])
solution()

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

Categories:

Updated:

Leave a comment