12865번 - 평범한배낭(dp)

문제:

여행에 가져갈 수 있는 N개의 물건이 있다. 물건들은 각각 W의 무게와 V의 가치를 지닌다.

배낭에는 최대무게 K만큼 넣을 수 있다.

배낭에 넣을 수 있는 물건들의 가치의 합의 최대값을 구하여라

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

 

풀이:

입력으로 아래와 같이 들어왔다고 생각해보자.

N=6, K=9

w=6, v=13

w=4, v=8

w=3, v=6

w=5, v=12

w=3, v=10

w=3, 3=11

1. 첫 입력으로 w=6, v=13 인 짐이 들어왔고, 무게 5까지는 아무것도 담지 못한다.
   6 이후로는 모두 가치의 최대값이 13이다.
   

   	1	2	3	4	5	6	7	8	9
   6 13	x	x	x	x	x	13	13	13	13

2. 이후 w=4, v=8 인 짐이 들어왔다.
   무게 3까지는 아직도 아무것도 담지 못하며, 무게 4, 5일때는 최대 가치가 8, 이후로는 그대로 13이다.
   이전 짐과 합치면 무게가 10으로 9가 넘어가므로 생각해주지 않아도 된다.
   

   	1	2	3	4	5	6	7	8	9
   6 13	x	x	x	x	x	13	13	13	13
   4 8	x	x	x	8	8	13	13	13	13

3. w=3, v=6인 짐이 들어왔다. 무게 2까지는 아무것도 담지 못하며, 무게 3일때, 가치의 최댓값은 6이다.
   무게 6까지는 이전과 최대 가치가 같다. 하지만 7부터는 달라진다.
   무게 7에서는 무게 3일때의 최댓값과 무게 4일때의 최댓값을 더한값을 고려해야한다.
   

   	1	2	3	4	5	6	7	8	9
   6 13	x	x	x	x	x	13	13	13	13
   4 8	x	x	x	8	8	13	13	13	13
   3 6	x	x	6	8	8	13	?	?	?

   지금 무게가 3인 짐의 가치는 6이며, 이전에 측정한 무게 4일때 최대 가치는 8로 합은 14이다.
   이전에 측정한 무게 7일때 최대 가치는 13으로,
   '지금 짐의 가치'와 이전에 측정한'7 - 지금 짐의 무게의 최대 가치'의 합인 14보다 작다.
   무게 7의 최대 가치는 14가 된다.
   즉 지금 노란색으로 표시한 곳과 초록색으로 표시한 곳의 합을 비교하고, 큰 값을 취하면 된다.
   
   

   	1	2	3	4	5	6	7	8	9
   6 13	x	x	x	x	x	13	13	13	13
   4 8	x	x	x	8	8	13	13	13	13
   3 6	x	x	6	8	8	13	14	14	19

   같은 원리로 무게 8일때와 무게 9일때 최대 가치가 변동되었다.
   
   
4.  위와 같은 방식으로 쭉 진행하다보면 아래와 같이 표가 나올 것이다.
   

   	1	2	3	4	5	6	7	8	9
   6 13	x	x	x	x	x	13	13	13	13
   4 8	x	x	x	8	8	13	13	13	13
   3 6	x	x	6	8	8	13	14	14	19
   5 12	x	x	6	8	12	13	14	18	20
   3 10	x	x	10	10	12	16	18	22	23
   3 11	x	x	11	11	12	21	21	23	27

   중복된 무게의 짐이 나와도 전혀 문제를 일으키지 않음을 알 수 있다.
   짐을 하나하나 체크하는 형태이기 때문이다.

 

전체코드:

코드로 표현하자면 아래와 같다.

import java.util.*;

public class 평범한배낭_12865번 {
    static int N, K;
    static int[] wList;
    static int[] vList;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // ~100
        K = sc.nextInt();

        wList = new int[N+1];
        vList = new int[N+1];
        dp = new int[N+1][K+1];

        for (int i = 1; i <= N; i++) {
            wList[i] = sc.nextInt();
            vList[i] = sc.nextInt();
        }

        findMax();

        System.out.println(dp[N][K]);
    }

    static void findMax() {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= K; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= wList[i]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wList[i]]+vList[i]);
                }
            }
        }
    }
}

wList와 vList에는 i번째 짐의 무게와 가치를 각각 저장해 놓았다.

findMax()메서드는 아래와 같이 작동한다.

1. 1번 짐부터 N번 짐까지 체크한다. -- i
   1. 무게 1 ~ K 까지 순환한다. -- j
      
      1. 먼저 dp[i][j]에는 dp[i-1][j]을 저장한다. 이전에 측정한 해당 무게에서의 최댓값을 먼저 적용시켜 놓는 것이다.
      2. 만약 현재 체크중인 무게(j)가 지금 체크중인 짐의 무게(wList[i])보다 크거나 같다면
         dp[i-1][j]와 dp[i-1][j-wList[i]]와 지금 체크중인 짐의 가치(vList[i])의 값을 비교해 큰 값을 저장한다.
         이 과정은 아래 표를 보면 이해될 것이다.
         

         	1	2	3	4	5	6	7	8	9
         6 13	x	x	x	x	x	13	13	13	13
         4 8	x	x	x	8	8	13	13	13	13
         3 6	x	x	6	8	8	13	13  vs 6 + 8	?	?

         풀이에서 보여준 표로, dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wList[i]]+vList[i]); 와 같은 역할을 수행중이다.

모든 과정이 끝나면 풀이에서 보여줬듯 아래와 같은 표가 생성이 될 것이다.

	1	2	3	4	5	6	7	8	9
6 13	x	x	x	x	x	13	13	13	13
4 8	x	x	x	8	8	13	13	13	13
3 6	x	x	6	8	8	13	14	14	19
5 12	x	x	6	8	12	13	14	18	20
3 10	x	x	10	10	12	16	18	22	23
3 11	x	x	11	11	12	21	21	23	27

 

고로 배낭에 담을 수 있는 최댓값은 dp[N][K]이다.

 

시행착오:

처음엔 무게가 중복될 경우를 생각하다가 사고가 조금 꼬여서 문제가 풀리지 않았다.

그래서 아래의 블로그를 참고하고, 나만의 생각으로 나만의 표를 작성해보았더니, 이해가 잘 되었다.

[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이) — 코오오딩 (tistory.com)

[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)

dp문제 골드단계로 넘어왔다고 갑자기 좀 어려워진 기분이다.

하지만 결국 풀었고, 풀이까지 작성할 수 있었다. dp에 더욱 자신감이 붙은 것 같다.