백준 22.03.01. 12865번 - 평범한 배낭

n, k = map(int, input().split())

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

for i in range(n):
    obj.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        wei = obj[i][0]
        val = obj[i][1]

        if j < wei:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wei]+val)

print(dp[n][k])

• dp는 위 사진과 같은 결과를 갖습니다.
• 우선 물건들을 저장할 리스트에 0무게의 0가치를 갖는(비어잇는) 요소를 하나 만들어줍니다.
• 그리고 모든 물건들을 반복문을 통해 추가해줍니다.
• 우선 dp는 허용된 모든 무게와 기준으로 삼을 물품마다의 최고 가치를 기록하기 위해서 허용된 무게만큼의 길이를 갖는 리스트를 물품의 개수만큼 갖습니다.
  • [[0]*(k+1) for _ in range(n+1)]
• 각 품목별로 무게를 비교해가며 dp를 채워나갈 것입니다.
• 이미 들어가있는 물품의 무게와 추가할 물품의 무게가 허용된 무게를 초과한다면
  • 1. 이미 있던 물건을 포기하거나
  • 2. 물건을 추가하지 않는 두가지 방법이 있습니다.
  • 이것을 if j < wei 조건문으로 걸러내어 만약 이 조건에 부합한다면 이전에 가장 큰 값을 가졌던 값을 계승합니다.
• 만약 그렇지 않다면 물건을 그대로 갖는것과 추가하는 것 중 큰 값어치를 갖는 것을 dp[i][j]에 기록합니다.
• 이 과정을 모두 거치고나면 dp의 제일 마지막 요소에 최댓값이 기록되므로 이것을 출력합니다.