평범한 배낭 - 이차원 행렬을 이용한 다이나믹 프로그래밍

풀이

바로 직전의 문제(https://velog.io/@hbtopkr/LCS-%EC%9D%B4%EC%B0%A8%EC%9B%90-%ED%96%89%EB%A0%AC%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D)와 거의 같다.

다음의 코드는 정답이다.

import sys 
input = sys.stdin.readline 
N, K = map(int, input().split())

items = [[0, 0]]
for _ in range(N):
    items.append(list( map(int, input().split())))

dp = [ [0 for _ in range(K+1)] for _ in range(N+1) ]

for i in range(1, N+1):
    for j in range(1, K+1):
        weight = items[i][0]
        value = items[i][1]
        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(value + dp[i-1][j-weight], dp[i-1][j])

print(dp[N][K])

변수 items를 만들어 받는 것이 첫 단추이다.
처음에 나는 이차원 행렬을 만들 생각을 못 하고 가치에 대한 배열과 무게에 대한 배열을 따로 받았었다....

for문 부분의 j는 "현재까지 누적된 무게"이다.