[백준] 12865번:평범한 배낭 (python 파이썬)

문제

www.acmicpc.net/problem/12865

 

풀이 및 소스코드

suri78.tistory.com/2

[백준알고리즘] 12865번: 평범한 배낭 -Python

이 분 티스토리를 참고했다.

원래는 입력을 받으면서 그때 그때 비교해주려고 하였으나, 틀렸다고 나온다.

그래서 w, v를 모두 입력 받고, 한 번에 비교해주었다.

저 위 티스토리를 보면 아주 잘 이해할 수 있다 !

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0]*(k+1) for _ in range(n+1)]
item = [[0,0]]

for i in range(n):
    item.append(list(map(int, input().split())))

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