[DP, 부분합, BFS, 냅색] 백준 / 골드 5 / 12865 평범한 배낭 / Python

문제

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

다음에 떠올려야할 사고 과정

'''
2초, 총 연산제한 2,000,000,000

최대(최소)화하기 위해 부분합으로 표현될 것? V

무엇에 대한 식으로 cache를 표현? 살펴본 물건 개수 n 및 베낭 가치 k 에 따른 식
cache[k][n] = max(cache[k-w][n-1] + v, cache[k-1][n])

총물건수 N <= 100
베낭최대 K <= 100,000
물건최대 W <= 100,000
물건가치 V <= 1,000

dfs 불가능
cache 존재해야함

# cf) 정해진 수량과 가치에 대해 무게를 최소화해야할 때
N 100 * V 1,000

# 정해진 수량과 무게에 대해 가치를 최대화해야할 때
N 100 * W 100,000 = 10,000,000

'''

풀이

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0]*(K+1) for _ in range(N+1)] # K는 1~K로 쓰고, N은 -1에 대비

for n in range(N):
    for k in range(1, K+1): # 1~K로 사용
        w, v = wv[n]
        if w > k:
            dp[n][k] = dp[n-1][k] # -1일 때 대비, n 살펴봤는데 업데이트 못하니까 아웃
        else:
            dp[n][k] = max(dp[n-1][k], dp[n-1][k-w] + v)
print(dp[N-1][K])