[골드5] 12865번 : 평범한 배낭

🛠 문제

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

👩🏻‍💻 해결 방법

전형적인 dp문제였지만 점화식을 세우는 것이 어려웠다...
dp 유형에 더욱 익숙해지도록 노력해야겠다

소스 코드

n, k = map(int, input().split())
data = [[0, 0]]
for _ in range(1, n+1):
  w, v = map(int, input().split())
  data.append([w, v])

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

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

print(dp[n][k])