[Java] 백준 12865번: 평범한 배낭

[문제 바로 가기] - 평범한 배낭

유형 : dp

2일 남은 현대오토에버 코딩테스트 대비로 풀이한 문제로 배낭 문제는 예전에 풀어봤지만 (당연히) 풀이가 기억나지 않아 참고했다.

💡 접근 방식

4 7
6 13
4 8
3 6
5 12

먼저 예제로 이해를 하면, 물건 개수 N은 4, 최대로 넣을 수 있는 무게 K는 7이다.
물건은 (무게, 가치)로 정리하면 (6, 13), (4, 8), (3, 6), (5, 12)가 있다.

배낭 문제의 핵심은 첫번째 물건부터 N번째 물건까지 배낭에 1. 넣을 것인지 2. 안 넣을 것인지를 결정하면 되는 것이다. 그리고 넣을 수 있는 최대 무게에 따라 가치의 최댓값을 갱신하면 되는데, 이를 위해 2차원의 dp[][] 배열을 선언한다.

사실 이해는 됐지만 그래서 이걸 코드로 어떻게 옮겨? 싶어서 표를 직접 그렸다.

---

• 행 : 물건 개수 N, 열 : 최대 무게 K
• 최대 무게에 따라 최대 가치를 구해야 함

1. 먼저 최대 무게가 0~2일 경우에는 아무것도 넣지 못한다.

	(6, 13)	(4, 8)	(3, 6)	(5, 12)
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3
4
5
6
7

2. 최대 무게가 3일 경우 (3, 6)인 3번째 물건을 넣을 수 있다.
   그리고 (5, 12)인 4번째 물건을 넣을지 안 넣을지 결정해야 하는데, 4번째 물건은 무게가 5이므로 최대 무게인 3을 초과한다.
   따라서 4번째 물건은 넣지 않고 가치의 최댓값은 6이 된다.

	(6, 13)	(4, 8)	(3, 6)	(5, 12)
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4
5
6
7

3. 최대 무게가 4일 경우 2번째 물건도 넣을 수 있게 된다.
   3번째에서는 (1) 2번째 물건을 그대로 둘 때와 (2) 2번째를 빼고 3번째를 넣은 가치를 비교해서 큰 값을 넣는다.
   dp[3][4] = Math.max(dp[2][4], dp[2][4 - 3] + 6);
   4번째에서는 무게가 초과하여 넣을 수 없으므로 dp[4][4] = dp[3][4]가 된다.

	(6, 13)	(4, 8)	(3, 6)	(5, 12)
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4	0	8	8	8
5
6
7

4. 이 과정을 반복하면 표가 다음과 같이 완성된다.
   단, 최대 무게가 7일 때
   (1) 1번째를 넣는다. (dp[1][7] = 13)
   (2) 1번째를 그대로 둘지, 1번째를 빼고 2번째를 넣을지 결정한다.
   dp[2][7] = Math.max(dp[1][7], dp[1][7 - 4] + 8)
   (3) 3번째는 dp[3][7] = Math.max(dp[2][7], dp[2][7 - 3] + 6)가 되는데 dp[2][7] = 13이고 dp[2][7 - 3] + 6 = 14가 되므로 14로 갱신된다.
   (4) 4번째도 마찬가지로 dp[4][7] = Math.max(dp[3][7], dp[3][7 - 5] + 12)가 되는데 dp[3][7] = 14고 dp[3][7 - 5] + 12 = 12가 되므로 14이 된다.

	(6, 13)	(4, 8)	(3, 6)	(5, 12)
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4	0	8	8	8
5	0	8	8	12
6	13	13	13	13
7	13	13	14	14

확실히 표를 그려서 이해하니까 이해가 쉬웠다. 배낭 문제를 더 풀어봐야겠다.

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 백준 12865번 평범한 배낭
 * - dp 
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int object[][] = new int[N + 1][2];
		int dp[][] = new int[N + 1][K + 1];
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			
			object[i][0] = Integer.parseInt(st.nextToken());
			object[i][1] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <= N; i++) {
			for (int w = 1; w <= K; w++) {
				if (w >= object[i][0]) dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - object[i][0]] + object[i][1]);
				else dp[i][w] = dp[i - 1][w];
			}
		}
		
		System.out.println(dp[N][K]);
	}
}