[자바/백준 골드5] #12865 평범한 배낭

🔒 골드5 - #12865 평범한 배낭

 

📌 테스트케이스 추가 힌트

5 7
6 13
4 8
3 6
5 12
2 7

= 19

 

 

✍️ 풀이법

 

대표적인 DP (다이나믹 프로그래밍) 문제이다. 

 

DP 문제를 해결해야할때, 가장 먼저 고려해야 하는 것은

캐싱을 통한 점화식 생성이다.

 

먼저 값을 저장할 DP 테이블 만든다.

가로축은 들 수 있는 무게를 의미하며,

세로축에는 차례대로 물건의 무게와 가치를 입력한다.

 

 

먼저 첫번째 물건인, 무게 6에 가치 13의 물건이 들어가게 되면,

무게 6까지는 들 수 없으므로 DP (캐시)에 6부터 채워지게 된다.

 

 

 

이후, 두번째 물건인 무게 4에 가치 8의 물건이 들어가게 되면,

마찬가지로 무게 4까지는 들 수 없으므로 이 전 값인 0을 가져오게 된다.

 

 

 

 

이후, 4부터는 두 번째 물건을 들 수 있으므로 8이 들어가게 된다.

하지만 6부터는 첫번째 물건을 드는 게 가치가 더 나가므로,

이전 DP 값인 13이 들어가게 된다.

 

 

 

마찬가지로 세번째 물건인 무게 3 가치 6 이 들어갔을 때,

3일 때, 6

4,5,6 일 때는 이전 DP의 값을 가져오게 된다.

 

 

 

 

 

여기서 중요한 7일 때 상황을 보면,

 

첫 번째 물건인 6을 들었을 때 13의 가치를 얻을 수 있지만,

두 번째와 세 번째를 같이 들었을 때 6+8=14의 가치를 얻을 수 있다.

 

다시 말해, 세 번째 물건이 추가되었을 때 7의 무게를 들 수 있는 경우는

이 전까지 경우에서 7을 드는 경우 ( 이 전 DP의 7을 드는 경우)와

이번 물건을 필수로 들게 되었을때 7을 드는 경우 중 큰 값의 경우가 된다.

 

 

이번 물건을 필수로 들게 되었을 때의 경우는

총 7의 무게에서 이번 물건의 무게( = 3)를 뺀 4의 무게를 드는 경우를 이 전 DP에서 찾으면 된다.

 

 

따라서, 이번 물건을 들지 않는 경우 13과이번 물건을 필수로 드는 경우 6+8=14 중

큰 값은 14이므로 14가 채워지게 된다.

 

 

 

 

네 번째 물건도 마찬가지로 채우게 되면 위와 같아진다.

 

 

 

 

 

백준에서 주어지는 네 번째 예시까지로는 이해가 덜 될 수 있으니,

테스트케이스 추가 힌트에 다섯 번째 예시(무게 2 가치 7)를 추가했다.

 

4까지는 쉽게 채울 수 있을 것이다.

 

 

 

 

다음 5의 경우를 보면, 이 전까지 5의 무게에서 최대 가치는 12였다.

하지만, 5의 무게에서 다섯 번째 물건을 필수로 드는 경우는

 

[(다섯 번째 물건의 가치) + { (들 수 있는 무게) - (다섯 번째 물건의 무게)}의 가치]와 같다.

 

둘 중, 큰 값을 채워주면 된다.

 

 

 

 

 

마찬가지로,

 

이 전까지 6 무게의 최대 가치는 13이고,

 

현재 물건 무게 2의 가치는 7,

6 - 2 = 4 이므로 4의 무게를 드는 최대 가치는 8이다. 7+8= 15

 

 

 

마찬가지로,

이 전까지 7 무게의 최대가치는 14,

 

현재 물건 2의 가치 7, 5의 가치 12 이므로, 7+12 = 19이다.

 

 

 

 

 

 

이제 위의 경우로 점화식을 도출하면 된다.

 

총 가치  =  최댓값 { 이전 물건까지의 가치,  현재 물건 가치   +  ( 총 무게 - 현재 무게)의 가치 }

dp [ i ][ j ] =  Math.max (  dp [ i-1 ][ j ]  ,  thing [ i ][ 1 ]   +    dp [ i - 1 ] [ j -  thing[ i ][ 0 ] ]  )

 

 

위와 같이 도출할 수도 있고,

 

dp [ i ][ j ] = thing[ i ][ 1 ]   +    dp [ i - 1 ] [ j -  thing[ i ][ 0 ] ]로 

단, dp [ i - 1 ] [ j ] 보다 크다는 조건을 걸어줄 수 도 있다.

 

 

 

 

 

위 문제의 경우, 1차원 배열로 풀어도, 2차원 배열로 풀어도 해결이 가능하다.

다만 1차원 배열로 풀기 위해서는 이 전 값을 저장하는 임시 배열이 필요하다.

 

아래 코드는 나의 풀이로, 배열보다는 List를 쓰는 것을 선호하기 때문에 List를 사용하여 해결하였다.

List 역시 임시 List인 newDp를 선언해주어 해결하였다.

 

 

 

🗝️ JAVA 풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class baekjoon12865 {

    static List<Integer> dp = new ArrayList<>();
    static List<int[]> things = new ArrayList<>();
    static int K;
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();
        for (int testCase = 0; testCase < N; testCase++) {
            int W = sc.nextInt();
            int V = sc.nextInt();

            int[] P = {W, V};
            things.add(P);
        }

        solve();
    }

    public static void solve() {
        for (int i = 0; i < K + 1; i++) {
            dp.add(0);
        }
        List<Integer> newDp = new ArrayList<>(dp);

        for (int index = 0; index < N; index++) {
            for (int i = things.get(index)[0]; i < K+1; i++) {
                if (dp.get(i) < things.get(index)[1] + dp.get(i - things.get(index)[0])) {
                    newDp.set(i, things.get(index)[1] + dp.get(i - things.get(index)[0]));
                }
            }

            dp = new ArrayList<>(newDp);

        }
        System.out.println(dp.get(K));
    }
}