[BOJ] 12865번 평범한 배낭

다음과 같이 dp를 정의하고 접근했다.

dp[i][j]: i번째 물건까지 최대 j무게로 했을 때 최대가치

N,K = map(int,input().split())
weight = [0]
value = [0]

for _ in range(N):
  w,v = map(int,input().split())
  weight.append(w)
  value.append(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 weight[i] <= j: # 들어갈 수 있음
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
    else: # 들어갈 수 없음
      dp[i][j] = dp[i-1][j]

print(dp[N][K])