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

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

12865번: 평범한 배낭

풀이

한 달 후면 국가의 부름으로 잡혀가는 준서가 여행을 간다고 한다.
준서가 견딜 수 있는 무게 내에서 최고의 가치를 찾는 문제이므로 dp 문제이다.

dp문제는 점화식만 찾으면 쉽게 해결할 수 있는 알고리즘으로 개인적인 팁을 주자면 필자는 dp 문제를 보면 공책에다가 표를 그려서 완전 탐색을 해본다. 물론 표를 그려본다고 쉽게 발견하지 못하는 문제도 많지만 반대로 표를 다 완성하기도 전에 점화식을 발견하는 경우도 있다.

위 문제의 예제를 표로 그려보면 다음과 같다.
우선 1번 물건부터 표현해보겠다.

 

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

 

1번 물건은 무게 6을 가지고 있기 때문에 무게 1 - 5까지는 담을 수 없다. 무게 6 - 7까지 13의 가치를 가질 수 있다.

 

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

 

이제부터 조금 달라진다. 2번 물건의 초기값은 이전 물건의 가치들이 담겨있을 것이다. dp 알고리즘은 누적을 하면서 최댓값을 찾아가기 때문이다. 2번 물건의 무게는 4로 무게 1 - 3까지는 담을 수 없다. 무게 4부터 8의 가치를 가진다.

 

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

 

3번 물건의 초기값 또한 2번 물건을 담은 후에 최대 가치를 그대로 받아온다. 받아온 최대 가치와 현재 물건의 가치를 비교하면서 큰 값을 입력해주면 된다. 여기서 가장 중요한 시점은 무게가 7에 도달했을 때이다. 3번 물건의 무게는 3, 무게 7에 도달했을 때 4의 무게가 남아있다.

남은 무게 4를 이전 물건에서의 최대값 8을 꺼내올 수 있게 된다. 즉, 무게 7의 최대 가치는 3번 물건의 무게3 (6) + 이전 물건의 무게 4 (8)을 더한 14 혹은 이전 물건의 무게 7에서 넘어온 13을 비교해서 더 큰 값을 입력하면 된다.

 

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

 

4번 물건의 초기값도 이전 물건의 최대 가치를 그대로 받아온다. 이후에 4번 물건의 무게는 5로 무게 6과 무게 7의 도달했을 경우에 무게 1, 2가 남는다. 하지만 이전 물건의 무게 1, 무게 2는 0이기 때문에 12 + 0 vs 무게 7의 이전 값 (14)를 하면
큰 값인 14가 되는 것이다.

글로 길게 작성했기 때문에 이해하는 게 어려울 것 같다.
우선 표를 보면 알 수 있듯이 2차원 배열의 dp를 생성하면 된다.

우선 점화식을 세우기 전에 무게 - N번 물건의 무게가 양수 일 경우와 음수 일 경우를 생각해야한다.
양수 일 경우에는 N번 물건을 넣었음에도 무게가 남는다는 뜻이다. 그렇기 때문에 남는 무게만큼의 이전 물건의 최댓값을 가져올 수 있다.

dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);

 

음수 일 경우에는 N번 물건을 넣을 수 없다는 뜻으로 그냥 이전 물건의 최대값을 가져오면 된다.

 

dp[i][j] = dp[i-1][j];

<최종코드>

import java.io.*;
import java.util.*;

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[] w = new int[N+1];
        int[] v = new int[N+1];
        
        for (int i=1; i<N+1; i++) {
            st = new StringTokenizer(br.readLine());
            
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }
        
        int[][] dp = new int[N+1][K+1];
        
        for (int i=1; i<N+1; i++) {
            for (int j=1; j<K+1; j++) {
                
                int next = j - w[i];
                
                // N번 물건을 넣어도 무게가 남는 경우
                if (next >= 0) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][next] + v[i]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
                
            }
        }
        
        System.out.println(dp[N][K]);
    }
}