[Python/파이썬][🥇5] 백준 알고리즘 12865 - 평범한배낭

📖[Python/파이썬][🥇5] 백준 알고리즘 12865 - 평범한배낭

📜문제

---

💡알고리즘

Dynamic Programming - DP (다이나믹 프로그래밍)

하나의 문제를 단 한 번만 풀도록 하는 알고리즘
#sub-solution #list #memoization

DP를 사용할 수 있는 조건

1. 큰 문제를 작은 문제(sub-solution)로 나눌 수 있을 때
2. 작은 문제에서 구한 솔루션으로 큰 문제의 솔루션을 구할 수 있을 때
3. 작은 문제들이 겹칠 때

👉🏻 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 문제. 
메모아이제이션(Memoization)이 사용됨(분할정복과 다른 이유). 
이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산할 때 단순히 값을 반환하기만 하면 되는 원리.

---

📕풀이방향

limit값과 무엇을 구하고자하는 문제인지 파악하는 것이 관건인 DP문제이다.
"최대 K만큼의 무게만을 넣을 수 있는 배낭"에서 "물건들의 가치의 최댓값"을 구하는 문제이므로 가치(V)값에 초점을 두고 해결하자.

---

📝알고리즘 구현순서

아래 표를 이해하면 DP로 쉽게 구현할 수 있다.

각 셀은 각 행 이전의 무게(W)와 가치(V)만 알고있다고 가정했을 때의 최대 가치의 합이다.
bag=[[W1,V1],[W2,V2], ...]로 가정해보자.

1. bag=[[6,13]]인 물건만 가지고 있는 경우
   K=0~5이면 아무것도 배낭에 담을 수 없으므로 V=0,
   K=6이상인 경우 W=6인 물건 단 하나만 담을 수 있으므로 V=13이다.
   
   
2. bag=[[6,13], [4,8]]인 경우
   K=0~3이면 V=0,
   K=4~5이면 V=8이 된다.
   그러나 K=6이상인 경우는 [4,8]보다 [6,13]이 V가 더 높기 때문에 V=13이다.
   
   
3. bag=[[6,13], [4,8], [3,6]]인 경우
   K=0~2이면 V=0,
   K=3이면 V=6,
   K=4~5이면 V=8,
   K=6이면 V=13이 된다.
   그러나 K=7일 때는 W=3인 물건과 W=4인 물건을 둘 다 담을 수 있으므로 V=14이다.

📌다시 표를 살펴보자.

[4,8]행에서 K=7일 때 [4,8]을 담는 것보다 [6,13]을 담는 것이 가치가 커서 V=13이라고 했다.
그러나 [3,6]행에서는 K=7일 때, [6,13]을 담는 것보다 [4,8]과 [3,6] 두개를 담는 것이 가치가 커서 V=14이다.

여기서 주의할 점은,
[4,8]행의 K=7일 때 값이 "13"인데 (노란음영),
[4,8]행에서 K=7인 값(13)보다 K=7-3일 때의 V(8) + [3,6]물건의 V(6)인 값이 더 크기때문에 V=14라는 것이다. (빨간음영의 합)
이 기준이 만족하지 않으면 DP[i][j] = DP[i-1][j]인 것을 확인할 수 있다!

DP[i][j] = max(DP[i-1][j], DP[i-1][bag[i-1][0]]+bag[i][1])
#표의 윗 셀과 현재물건의V+이전물건의V값의 최댓값이 바로 DP값임

코드를 보면서 다시 살펴보자.

---

💻결과코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
bag = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(K+1) for _ in range(N+1)]
#DP표는 0~K+1, 0~N+1로 구성하자 (N=1일 때, DP[i-1][j]가 존재해야 하므로)

for i in range(1,N+1):
    for j in range(1,K+1):
        if j >= bag[i-1][0]:  #"현재최대무게j가 해당물건무게보다 큰 경우
        #표의 윗 셀의 값과 현재물건의V+이전물건의V값의 최댓값을 DP[i][j]에 저장
            dp[i][j] = max(bag[i-1][1]+dp[i-1][j-bag[i-1][0]],dp[i-1][j])
        else:
        	#"현재최대무게j가 해당물건무게보다 작은 경우 (현재 물건을 담을 수 없는 경우)
            dp[i][j] = dp[i-1][j]

print(dp[N][K])  #DP[N][K]가 무조건 정답

---

📚정리

위에서 동작원리 설명은 다 했으므로 몇 가지 체크사항에 대해서만 정리해보려고 한다.

1. DP가 N+1행, K+1열인 이유?
   N=1인 경우, DP[i-1][j]값이 존재해야 한다.
   즉, 아무것도 담지 않은 빈 배낭의 상태를 초기화 해놓기 위해 0행, 0열이 필요하다.
   
   
2. j >= bag[i-1][0] 에서 bag의 i값을 i-1으로 비교하는 이유?
   우선 bag리스트는 [[6,13], [4,8], [3,6]...]이렇게 저장되므로 0행이 첫 번째 값이다.
   즉 DP에서 0번째 물건이 0, 1번째가 [6,13]인데, bag에서는 0번째 물건이므로 1씩 차이가 난다.
   
   
3. j >= bag[i-1][0] 에서만 max값으로 비교하는 이유?
   현재최대무게 j가 현재물건의무게(bag[i-1][0])보다 작다면 현재물건을 담을 수 없기 때문이다.
   이 경우가 아니면 DP[i][j] = DP[i-1][j]을 따른다.
   👉🏻 해당 셀의 윗 셀이 현재최대무게j에서 최댓값이기 때문
   👉🏻 윗 셀을 계속 사용할 수 있으므로 추가 계산이 필요없다 (DP)

   ex) [4,8]인데 j가 3인 경우
       최대무게가 3이면, 무게가 4인 물건은 담을 수 없다!