[BOJ]12865 평범한 배낭

[문제 링크]

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

[풀이]

동적계획법으로 풀어야 하는 문제다.

각 무게마다 담을 수 있는 최대의 가치를 dp배열에 저장해가며 풀었다.

구체적으로 새 무게/가치 짝이 들어오면 이미 dp배열에 존재하는 값들을 이용해 새로 가능한 무게들을 만들어보고 해당하는 무게의 가치가 이전에 존재하는 무게/가치보다 높으면 새 값을 dp에 저장하는 방법으로 짰다.

dp는 항상 어렵다...

[정답 코드]

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())

wv_arr = [] #무게/가치 배열
for _ in range(n):
    wv_arr.append(list(map(int, input().split())))

dp = [0] * (k + 1)
for w, v in wv_arr:
    if w <= k:
        temp = deque()
        for i in range(1, k - w + 1):
            temp.append(max(dp[i + w], dp[i] + v))
        dp[w] = max(dp[w], v)
        for i in range(k - w):
            dp[i + w + 1] = temp.popleft()


print(max(dp))