[백준 12865번] 평범한 배낭 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N,K = map(int,input().split())

WV = []
dq = deque()

for i in range(N):
  WV.append(list(map(int,input().split())))

DP = [[0]*(K+1) for i in range(N+1)]

for i in range(1,N+1):
  w,v = WV[i-1]
  for weight in range(1,K+1):
    if weight < w:
      DP[i][weight] = DP[i-1][weight]
    else:
      DP[i][weight] = max(DP[i-1][weight-w]+v,DP[i-1][weight])
  
print(DP[N][K])

무려 일주일 넘게 끙끙대면서 풀지 못했던 문제다.

 

답지 안보고 풀려고 애쓰다가 결국은 답지를 보고 말았는데, "냅색(Knapsack) 알고리즘"의 전형적인 문제였다.

 

이런 문제는 생각한다고 생각할 수 있는 문제가 아니기 때문에 본인이 천재가 아니라면 아이디어를 떠올리는 것보다는 공부하는것이 맞을 것이다.

 

 

 

오늘의 교훈) 안풀리는 문제를 너무 오래 붙들고 있지 말자