[백준]12685(파이썬) - 평범한 배낭

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

12865번: 평범한 배낭

 

• 이제는 문제를 읽었을 때, 어떻게 풀어야 하는지 방향성에 대한 확신이 약 80프로 정도 생긴 것 같습니다. 100프로 확신이 될 때까지 문제를 많이 풀어봐야겠군요.
• 이 문제를 읽고 나서는, 무조건 DP 문제인데,,, 많이 본 문제 유형이긴 한데 제가 한 번에 떠오르는 방식으로는 구현할 수 없었습니다.
• 처음에 접근할 때 주어진 물건들이 각각 취할 수 있는 액션을 생각해보았고, 가방에 물건을 넣을 때, 뺄 때로 구분할 수 있었습니다.
  하지만 제가 생각한 액션의 시간복잡도는 2 ^ n 이기 때문에 주어진 조건에서 n이 최대 100일 경우, 당연히 시간 초과가 발생하겠죠?
• 역시 DP는 손으로 하나하나 그려보는 것이 최고인 것 같습니다. 하나하나 그리다 보니 아래와 같은 표를 작성할 수 있었습니다.
  

  

• 이해가 되셨나요? 설명을 해보자면, 주어진 물품을 넣었을 때 k 보다 작은 범위안에 있다면 해당 무게의 자리에 가치를 입력해줍니다.
  우리가 알고 싶은건 주어진 k 무게 범위 안에서의 최대 가치이기 때문에 물건을 넣었을 때, 무게가 k를 초과한다면 신경 쓰지 않아도 됩니다. 
• 먼저 A 물건을 넣으면 6 의 무게에 가치 13을 가지게 됩니다.
• 다음으로 B 물건을 넣으면 4의 무게에 8의 가치를 얻게 되고, 가치가 있는 6의 무게에 4의 무게를 더하면 7이 넘어가므로 고려하지 않습니다.
• 다음  C 물건을 넣으면, 3의 무게에 6의 가치를 얻게 되고 가치가 있는 4의 무게에 3의 무게를 더하면 7이 되므로 두 물건의 가치를 더해서 7의 무게일 때 가치 자리에 넣어줍니다.
• 이런 식으로 생각 해서 점화식을 구한 뒤, 문제를 풀어주면 됩니다.

 

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
w = [0 for _ in range(n+1)]
v = [0 for _ in range(n+1)]
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
for i in range(n):
    a,b = map(int,input().split())
    w[i] = a
    v[i] = b

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