[Python] 백준 12865번 - 평범한 배낭

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

12865번: 평범한 배낭

 

냅색 분명히 학교 수업 때 배웠는데 .. 강의 자료 안 보고 하려니까.... 머리에 쥐날 뻔 했다...

어떤 식으로 풀어야 할 지 감이 안 잡혀서 DP테이블 직접 그렸다. 앞으로 DP 문제 풀 때는 테이블 구상하는 방법을 생각해서 접근해야지.

else 부분 max 비교 대상을 찾는 게 관건이었고 그것만 하면 어렵지 않았다.

 

n, k = map(int, input().split()) #n: 물품의 수, k: 버틸 수 있는 무게
weight = [0 for _ in range(n+1)]
value = [0 for _ in range(n+1)]
dp = [[0 for j in range(k+1)] for i in range(n+1)]

for i in range(1, n+1):
    w, v = map(int, input().split()) #w: 각 물건의 무게, v: 해당 물건의 가치
    weight[i] = w
    value[i] = v

for i in range(1, n+1):
    for j in range(1, k+1):
        if weight[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

print(dp[-1][-1])