# 12865 평범한 배낭 -

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

12865번: 평범한 배낭

n, k = map(int, input().split()) # n 은 물건의 수 k 는 총 무게 

w = [0]*n 
v = [0]*n 

for i in range(n):
  w[i],v[i] = map(int,input().split())

dp = [ [0]*(k+1) for _ in range(n+1) ] 

for i in range(n+1):
  for j in range(k+1):
    if w[i-1] <= j:
      dp[i][j] = max( v[i-1]+ dp[i-1][j-w[i-1]], dp[i-1][j] )
    else:
      dp[i][j] = dp[i-1][j]

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

 

내가 헷갈렸던 것.. 

 

점화식 까지는 접근 했음. 

그런데, dp 의 기준을 only 무게로 잡아서,  만약 무게가 6 인 경우 3+3 이 최대가 되면 어떻게 하는지 고민을 많이 함. 

->  순차적으로 물건이랑 무게 둘 다 를 기준으로 하는 dp 를 선언하면 해결됨. 

 

그리고 w[i-1] > i 인 경우에 대해서 생각하지 못했음. 

못 들어가면 그 전의 값으로 초기화 해주기. 

 

 

맨날 문제가 비슷하면서도 잘 안 풀린다. 

아직 잘 모른다는 뜻인 것 같다. 

잘 설명해둔 블로그를 찾았다. 참고하기. 

 

# Reference 

https://dojinkimm.github.io/algorithm/2019/10/19/dp-2.html

Study Blog