평범한 배낭

백준 12865번: 평범한 배낭

아이디어

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))

여담

냅색 알고리즘이라고 좀 유명한 문제였다. 아무런 검색도 없이 자력으로 풀어서 기분이 상당히 좋다.