[정글 알고리즘] - [중] 백준12865- 평범한 배낭- 골드5

 

한 줄 해설과 용량별 DP 변화 중심으로 정리한 상세형 버전이다.

1. 문제를 아주 짧게 말하면

무게 제한 K 안에서 여러 물건 중 일부를 골라 담을 때 얻을 수 있는 가치의 최댓값을 구하는 전형적인 0/1 배낭 문제다. 물건은 각각 한 번만 사용할 수 있다. [Source](https://www.acmicpc.net/problem/12865)

2. 핵심 아이디어

dp[i][cap]의 뜻

앞에서 i개 물건만 고려했을 때, 가방 용량 cap으로 얻을 수 있는 최대 가치

• 현재 물건을 안 넣으면: dp[i-1][cap]
• 현재 물건을 넣으면: dp[i-1][cap-weight] + value

3. 전체 코드

1import sys

2

3input = sys.stdin.readline

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

5items = [tuple(map(int, input().split())) for _ in range(n)]

6

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

8

9for i in range(1, n + 1):

10 weight, value = items[i - 1]

11 for cap in range(1, k + 1):

12 if cap < weight:

13 dp[i][cap] = dp[i - 1][cap]

14 else:

15 dp[i][cap] = max(dp[i - 1][cap], dp[i - 1][cap - weight] + value)

16

17print(dp[n][k])

4. 코드 한 줄씩 설명

줄	코드	설명
3	input = sys.stdin.readline	input 함수를 sys.stdin.readline으로 바꿔 입력 속도를 높인다.
4	n, k = map(int, input().split())	물건 개수 n과 배낭 허용 무게 k를 입력받는다.
5	items = [tuple(map(int, input().split())) for _ in range(n)]	각 물건의 (무게, 가치)를 리스트에 저장한다.
7	dp = [[0] * (k + 1) for _ in range(n + 1)]	dp[i][cap]는 앞에서 i개 물건만 고려했을 때 용량 cap으로 만들 수 있는 최대 가치를 뜻한다.
9	for i in range(1, n + 1):	첫 번째 물건부터 차례대로 고려한다.
10	weight, value = items[i - 1]	현재 살펴보는 물건의 무게와 가치를 꺼낸다.
11	for cap in range(1, k + 1):	현재 용량을 1부터 k까지 바꿔 가며 계산한다.
12	if cap < weight:	현재 용량이 물건 무게보다 작으면 이 물건은 넣을 수 없다.
13	dp[i][cap] = dp[i - 1][cap]	넣을 수 없으니 바로 위 행의 값, 즉 이전 물건들만 고려한 최적값을 그대로 가져온다.
14	else:	현재 물건을 넣을 수 있는 경우다.
15	dp[i][cap] = max(dp[i - 1][cap], dp[i - 1][cap - weight] + value)	안 넣는 경우와 넣는 경우를 비교해 더 큰 가치를 선택한다.
17	print(dp[n][k])	모든 물건을 고려했을 때 용량 k에서의 최대 가치가 정답이다.

5. DP 테이블 시각화

이해용 예시로 물건 (6,13), (4,8), (3,6), (5,12), 용량 7을 사용했다.

물건 \ 용량	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

6. 물건이 하나씩 추가될 때 배열 변화

물건 1: 무게 6, 가치 13

이 물건까지 고려한 뒤 각 용량에서 얻을 수 있는 최대 가치

dp[1] = [0, 0, 0, 0, 0, 0, 13, 13]

물건 2: 무게 4, 가치 8

이 물건까지 고려한 뒤 각 용량에서 얻을 수 있는 최대 가치

dp[2] = [0, 0, 0, 0, 8, 8, 13, 13]

물건 3: 무게 3, 가치 6

이 물건까지 고려한 뒤 각 용량에서 얻을 수 있는 최대 가치

dp[3] = [0, 0, 0, 6, 8, 8, 13, 14]

물건 4: 무게 5, 가치 12

이 물건까지 고려한 뒤 각 용량에서 얻을 수 있는 최대 가치

dp[4] = [0, 0, 0, 6, 8, 12, 13, 14]

7. 중요한 칸 직접 따라가기

dp[1][6] = 13

용량 6에서 첫 물건을 담으면 13, 안 담으면 0이므로 13 선택

dp[2][4] = 8

용량 4에서 두 번째 물건만 담을 수 있어 8 선택

dp[3][7] = 14

용량 7에서 세 번째 물건(3,6)을 담고 남은 4칸 가치 8을 더해 총 14가 가능

dp[4][7] = 14

용량 7에서 네 번째 물건을 담으면 dp[3][2]+12=12, 안 담으면 14라서 그대로 14 유지

8. 자주 헷갈리는 포인트

• 이 문제는 0/1 배낭이라 같은 물건을 여러 번 쓰면 안 된다.
• 현재 행에서 현재 행을 참조하면 중복 사용 문제가 생긴다. 그래서 2차원 DP는 항상 위 행을 본다.
• 최대 가치 문제지, 물건 개수를 최대화하는 문제가 아니다.

9. 복잡도

시간 복잡도는 O(NK) 이다.

공간 복잡도도 2차원 DP 기준 O(NK) 이다.

원문 문제 링크

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