[BOJ - JAVA] 12865 - 평범한 배낭 (DP)

# 주소

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

12865번: 평범한 배낭

# 문제

# 문제 해설 및 코드 리뷰

두 가지로 풀었습니다.

처음엔 백트래킹이 시간이 더 절약될 줄 알고 백트래킹으로 풀었다가 예제 문제 정답은 맞는데 시간초과가 떠서 DP로 풀어야 했습니다.

import java.util.*;
public class Main{
    static int sum = 0;
    static int n,m;
    static int[] arr,value;
    static boolean[] visit;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n];
        value = new int[n];
        visit = new boolean[n];
        for(int i = 0; i < n; i++){
            arr[i] = scan.nextInt();
            value[i] = scan.nextInt();
        }
        for(int i = 1; i <= n; i++){
            dp(0,i, 0,0);
        }
        System.out.println(sum);
    }
    public static void dp(int count,int x, int y, int t){
        if(count == x){
            if(y > m)
                return;
            else
                sum = Math.max(t,sum);
            return;
        }

        for(int i = 0; i < n; i++){
            if(!visit[i]){
                visit[i] = true;
                dp(count+1, x, y+arr[i], t + value[i]);
                visit[i] = false;
            }
        }
    }
}

DP문제 풀이를 확인합시다.

import java.util.Scanner;

public class Main {

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

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] arr = new int[n+1]; //물건들의 무게를 담는다
        int[] value = new int[n+1]; //물건들의 가치를 담는다

        for(int i = 1; i<n+1; i++) {
            arr[i] = scanner.nextInt();
            value[i] = scanner.nextInt();
        }

        int[][] dp = new int[n+1][m+1];

        for(int i = 1; i<n+1; i++) {
            for(int j = 1; j<m; j++) {

                if(arr[i]<=j) { //해당 물건을 가방에 넣을 수 있다.
                    //그냥 물건을 안넣거나, 물건을 넣거나
                    dp[i][j] = Math.max(dp[i-1][j], value[i]+dp[i-1][j-arr[i]]);
                }else { //해당 물건을 가방에 넣을 수 없다
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(dp[n][m]);
    }

}

유명한 냅색문제라고 하는데 처음 듣네요 (하하..)

DP에 제가 유독 더 약해서 이해안되는게 정말 많았습니다.

다른 분들이 푸신 것들을 여러개 보고 제 것으로 만들기 위해서 어떻게 흡수할지 고민도 많이했습니다.

대부분의 난이도 있는 DP문제들은 2차원 배열로 많이 풀곤 합니다.

그래서 이 방법에 익숙해져야겠습니다.

이 문제를 이해하려면 dp[i][j] 는 dp[i-1][j]를 가지고 있다는 사실에 유념하셔야 겠습니다.

따라서 만약 arr가 j보다 작다는 것은 물건을 가방에 넣을 수 있다라는 얘기가 되고

이때 dp에는 dp[i-1][j]와 dp[i-1][j-arr[i]]에 새로운 value[i]값을 더한 것 중에 큰 것을 dp에 담습니다.

그런데 만약 arr가 j보다 크다면 물건을 넣을 수 없으므로 dp는 이전 dp[i-1][j]로 돌려놓습니다.

참 이색적인문제에요.

dp는 풀어도 풀어도 제 것으로 만들기 힘드네요..