풀이 참고 사이트 알고리즘 요약

가방 크기	0	1	2	3	4	5	6	7	8	9	10	11	12
루비	0	0	0	6	6	6	6	6	6	6	6	6	6
다이아	0	0	0	6	6	6	6	9	9	9	9	9	9
사파이어	0	0	0	6	6	6	6	9	11	11	11	11	11

• 행 ($i$): $i$번째 물건까지 고려했을 때
• 열 ($w$): 배낭의 현재 용량이 $w$일 때값
• $DP[i][w]$: $i$번째 물건까지 고려하고 배낭 용량이 $w$일 때 가질 수 있는 최대 가치

💎 루비를 선택하는 경우(dp[루비])

💎 다이아를 선택하는 경우
(dp[다이아] = 각 무게별로 [루비, 다이아]에서 만들어낼 수 있는 최대 가치합)

💎 사파이어를 선택하는 경우
(dp[사파이어] = 각 무게별로 [루비, 다이아, 사파이어]에서 만들어낼 수 있는 최대 가치합)

• 가방의 크기가 7인 경우,
  • 사파이어를 챙길 경우
    남은 공간 2, 남은 공간이 2일 경우 루비, 다이아 두가지 보석 모두를 이용해도 더 넣을 수가 없으므로 가치는 5,
  • 사파이어를 챙기지 않은 경우
    이전에 구해둔 9가 최대이기 때문에 최대이윤은 9가됩니다.
• 가방의 크기가 8인 경우
  • 사파이어를 챙길 경우, 남은공간은 3, 이미 테이블을 통해 가방의 크기가 3일 때 루비/다이아를 이용해 구할 수 있는 최대 이윤은 6임을 구했습니다.
    사파이어 가치 5 + ~다이아까지 넣을 떄 최대이윤 6 = 11, 즉 최대이윤이 11이 됩니다.

현재 내가 구하려고 하는 셀의 값은
MAX(현재 보석의 가치+남은가방크기만큼 나머지 보석을 넣을 때 최대 가치, 이전까지 구해둔 보석의 가치)

즉,
ans[i][j] = max(profit[i] + ans[i-1][j-weight[i], ans[i-1][j]]

---

최종 코드

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

weight = [0]
value = [0]

for i in range(n):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

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

# dp 리스트 채우기
for i in range(n+1):
    for j in range(1, k+1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i-1][j-weight[i]], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

# 최종 답
answer = max(dp[n-1])

print(answer)

• DP의 행과 열을 1-based로 한 이유 (DP가 N+1행, K+1열인 이유)
  N=1인 경우, DP[i-1][j]값이 존재해야 한다.
  즉, 아무것도 담지 않은 빈 배낭의 상태를 초기화 해놓기 위해 0행, 0열이 필요하다.

---

배운 점 정리

도무지 모르겠어서 풀이 참고 사이트 를 참고했다.

dp[i] = i요소를 반드시 포함하는 경우의 최대 가치의 합 까지는 알고리즘을 떠올려봤는데, [루비] → [루비, 다이아] → [루비, 다이아, 사파이어] 이런식으로 요소들을 누적시켜서 계산할 생각은 못했다. (그게 바로 DP의 핵심인데 왜 못떠올렸을까...)

처음엔 n행은 0-based로, k열은 1-based로 설정하였다. 그래서 dp[0][]을 초기화한 후 dp[1][]부터 순회하도록 구현했다. 그러나 행또한 1-based로 하면 굳이 초기화 코드가 없어도 된다는걸 깨닫고 행과 열 모두 1-based로 수정했다.