[백준] 12865번 평범한 배낭(java)

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

12865번: 평범한 배낭

핵심

백트래킹을 사용하여 풀면 시간초과가 뜨게 된다.

따라서 이 문제는 DP를 사용해야 한다.

 

우선 물건 1개를 넣을 때 각 무게당 최대 가치는 어떻게 구할 수 있을까?

당연하게도 위와 같다.

1~5에는 6의 무게를 넣을 수 없기 때문이다.

저 자리에 0이 들어가는 것이 맞을까? 당연하게도 6이 들어가는 게 맞다.

3의 가치를 넣을 수 있기 때문이다. 이러한 방식으로 7까지 가면 8인 상태여야 할까? 아니다. 3+4 = 7 이 되기 때문에, 14가 된다.

이러한 방법을 사용하면 아래와 같은 테이블을 만들 수 있다.

 

또한 점화식도 구할 수 있게 된다.

물건을 담을 수 없는 경우(j <w) dp [i][j] = dp [i-1][j]

물건을 담을 수 있는 경우(j>=w) dp [i][j] = Math.max(dp [i-1][j] , dp [i-1][j-w]+v)가 된다.

 

우측하단의 경우 최댓값이 설정된다.

 

정답 코드

import java.util.Scanner;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] dp = new int[N+1][M + 1];

        for (int i = 1; i<=N; i++){
            int w = sc.nextInt();
            int v = sc.nextInt();

            for (int j = 1; j<=M; j++){
                if (w>j)dp[i][j] = dp[i-1][j];
                else dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w] + v);
            }
        }
        System.out.println(dp[N][M]);
    }
}

해설

위에서 이미 설명한 대로 코드를 작성하였다.

각 아이템들의 경우 굳이 배열을 만들지 않고, 입력을 받는 즉시 dp에 값을 채워 넣었다.

 

 

배운 점

백트래킹을 사용하면, DP를 사용할 때보다 코드도 복잡해지고, 시간복잡도 측면에서도 매우 부적절하다.

DP의 감을 익히고 더 많은 문제를 풀어야겠다.