오잉,.,,,? 언제 다 풀었었담...? 아마 대부분이 c++ 한창 공부할 때 풀어뒀던 것 같다.
과거의 내가 더 똑똑한 것 같다.
내 제출
import sys
input = sys.stdin.readline
n, k = map(int, input().rstrip().split())
wv_list = []
# n개의 줄에 거쳐 각 물건의 무게 w, 물건의 가치 v
for i in range(n):
w, v = map(int, input().rstrip().split())
wv_list.append((w, v))
# 물건은 아예 담지 않는 0번부터 n 번까지 총 n+1
# 배낭의 무게가 0부터 k 인 경우까지, k+1
# 각각의 최대 가치
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = wv_list[i - 1]
for bag_weight in range(k + 1):
# 현재 확인하려는 물건의 무게(weight)와 가방의 무게 비교
# 물건이 무거워서 가방에 못 넣는 경우
if weight > bag_weight:
dp[i][bag_weight] = dp[i - 1][bag_weight]
else:
dp[i][bag_weight] = max(dp[i - 1][bag_weight], dp[i - 1][bag_weight - weight] + value)
print(dp[n][k])
