dp테이블에 각 무게에서 담을 수 있는 무게중에 가치가 최대인 경우를 저장한다.(인덱스가 무게임)
이렇게 저장하면 막 "물건 이거 넣어봤다가.. 다른거 다시 넣어봤다가.." 이런 슬픈 완전탐색을 할 필요 없이 가방에 넣을 수 있는 최대한의 가치를 구할 수 있다.
import sys
import copy
input = sys.stdin.readline
N, K = map(int, input().split())
dp = [0] + [-1] * K
dp2 = [0] + [-1] * K
for _ in range(N):
w, v = map(int, input().split())
for i in range(K - w + 1):
if dp2[i] != -1:
dp[i + w] = max(dp[i + w], dp2[i] + v)
dp2 = copy.deepcopy(dp)
print(max(dp))
냅색 알고리즘이라고 좀 유명한 문제였다. 아무런 검색도 없이 자력으로 풀어서 기분이 상당히 좋다.