[Backjoon] 골드 5 평범한 배낭

문제: 골드 5 평범한 배낭 

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

풀이코드

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

dp = [[0] * (k+1) for _ in range(n+1)]
## dp[i][j] = i번째 물건까지 넣었을 때 무게 j 이하로 얻을 수 있는 최대 가치

for i in range(1, n+1): 
    w, v = map(int, input().split())
    for j in range(1, k+1): 
        if w <= j: 
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else: 
            dp[i][j] = dp[i-1][j]
print(dp[n][k])

---

느낀 점

일단 DP에선 최대를 어떻게 기존의 값을 사용해 구할 수 있는지를 생각해야 할 것 같다. 

일단 dp라는 2차원 리스트를 만들어 각 행은 물건의 종류, 각 열은 무게로 잡았다. 

그래서 dp[i][j]는 i번째 물건까지 넣었을 때 무게 j 이하로 얻을 수 있는 최대의 가치를 의미한다. 

일단 어떻게 풀어야 할지 잘 감이 안 잡혀서 예시를 다 써봤다. 

4 7
6 13
4 8
3 6
5 12

예제는 다음과 같고 맨 첫 줄엔 물품의 수 n과 버틸 수 있는 무게 k가 주어진다. 

 

일단 첫 번째 물건을 넣었을 땐 첫 번째 물건의 무게가 6이기 때문에 무게 6부터 가치가 채워지고 무게 7까지 할 수 있다 해도 물건이 1개이기 때문에 13으로 가치가 채워진다. 

	무게 0	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
물건 0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	13	13
물건 2
물건 3
물건 4

 

그 다음 무게가 4이고 가치가 8인 물건이 들어오면 무게 6까지 갔을 때 첫 번째 물건만 담는 게 더 가치가 커서 무게 6부턴 13이 표시되어야 한다. 

	무게 0	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
물건 0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	13	13
물건 2	0	0	0	0	8	8	13	13
물건 3
물건 4

 

그 다음 무게가 3인데 가치가 6인 물건이 들어오면 다음과 같이 dp 리스트가 채워진다. 

	무게 0	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
물건 0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	13	13
물건 2	0	0	0	0	8	8	13	13
물건 3	0	0	0	6	8	8	13	14
물건 4

 

마지막으로 무게가 5이고 가치가 12인 물건이 들어오면 ...

	무게 0	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
물건 0	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	13	13
물건 2	0	0	0	0	8	8	13	13
물건 3	0	0	0	6	8	8	13	14
물건 4	0	0	0	6	8	12	13	14

 

와 같이 최종 dp 리스트가 완성된다. 

 

이런 식으로 직접 쓰면서 이해하면 코드 짜기가 훨씬 수월한 것 같다.