DP를 연습하고 마주했던 벽이어서 작성을 해보고자 한다.

문제

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

풀이 핵심

인터넷에 배낭 문제, knapsack 등을 검색하면, 점화식이 나오는데 점화식을 보고 이해가 잘 안된다.

관련해서 좋고 좀 더 분석적인 글을 보고 싶다면 0-1 knapsack 등으로 검색해보거나, DP의 예로 유명한 배낭 문제이므로 조금 찾아보면 나올 것이다.

DP 배열의 형태

DP배열에 어떤 값이 들어갈지는 앞서 DP 문제를 몇 가지 봤다면 예상되겠듯이,V인 가치이다. 각 DP[][] 위치에는 최대의 가치를 저장하는 것이다.

크기
배열의 크기도 정해야 한다. 이때 배열의 크기는 DP[N+1][K+1]로 저장하게 되는데, 이유는 아래 문제 풀이를 보다보면 이해할 수 있을 것이다. 요약하자면 다음과 같다.

• 물건의 갯수 N과 최대 무게 K에 대하여, 무게에 따른 최대 가치를 저장하는 것이다.
• 이때 각 물건을 저장했을 때에 대한 행 row와 무게를 뜻하는 열 col을 통해서 계산하는 것이다.

핵심 풀이
이 평범한 배낭이라는 문제는 입력 N개가 들어왔을 때, 각 i에 대하여 다음과 같이 나눌 수 있다.

1. 배낭의 i를 넣은 경우
2. 배낭의 i를 제외한 경우

두 가지를 구분하기 위해서는 다음과 같은 표를 이해해야한다.

1행에서는 6kg을 담을 수 있을 때, 13의 가치를 얻을 수 있다.
2행에서는 4kg을 담을 수 있을 때, 8의 가치를 얻을 수 있지만, 6kg을 담을 수 있을 때에는 1행에서 담았던 6kg의 가치가 더 크기 때문에 13의 가치를 얻는다.

(2, 6) 입장에서 생각했을 때, 가능한 무게가 6이라면 dp[]에 저장되는 것은 다음과 같은 두가지다.

1. 4kg, 8$를 저장하고 남은 무게만큼 최적의 DP를 더하는 경우 → 8 + dp[i-1][6-4]
2. 4kg, 8$를 저장하지 않고, 이전 행에서 같은 6kg일 때 최적의 값이었던 경우 → dp[i-1][6]

Math.max()를 통해 더 큰 것을 저장하면서 진행하면 된다.

구현

public class Knapsack {
    static int[][] dp;
    static int[] weight;
    static int[] valueOf;
    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());
        weight = new int[N + 1];
        valueOf = new int[N + 1];
        dp = new int[N + 1][K + 1];
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            valueOf[i] = Integer.parseInt(st.nextToken());
        }

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

풀이 방법

1. 이론을 적용하기 위해서 dp[N+1][K+1]로 초기화를 해준 뒤, 각각의 무게와 가치를 N+1만큼 입력받는다.
2. 이제 dp[][]배열을 채워나간다. 1,1부터 시작해서 j는 현재 담을 수 있는 무게를 뜻하므로, if(weight[i] > j) 즉, 현재 담을 수 있는 무게보다 지금 담으려는 물건 무게가 더 무겁다면 안넣고 이전 값을 받는다.
   dp[i][j] = dp[i-1][j] → 참고로 위 표에서는 4,3에서 5kg을 못담아서 3,3의 있는 값을 가져오는 경우
3. 만약 무게를 담을 수 있다면, 어떤 가치가 더 큰지 비교해야 한다.
   1. dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + valueOf[i])
   2. Math.max(현재 물건을 제외한 최대 가치, 현재 물건을 포함한 최대 가치)를 뜻한다.
4. 출력은 dp[N][K]를 통해 최대 무게의 모든 물건을 확인한 dp[][]배열을 출력한다.

마치며

DP 알고리즘을 단계적으로 연습하면서 비슷한 패턴을 발견할 수 있었는데, 처음보는 패턴을 발견해서 되게 당황했었다.
처음 발견했던 문제는 안녕이라는 문제를 풀면서 벽을 느끼고 더 이상 고민하는 것에 힘이 빠져 정답을 찾아다녔었다. 보통 코드를 보면 풀이가 이해됐는데, 전혀 이해가 안돼서 찾아보니 knapsack이라는 것을 찾게 됐다.

여튼 안녕이라는 문제를 정답을 보고 풀이한 뒤, 비슷하다는 배낭 문제를 찾아서 풀었는데 바로 풀 수 있어서 기분이 많이 좋고 발전되는 느낌이 들었다.

그 외 가벼운 DP 적응 문제들은 DP 알고리즘을 정의한 글에 정리해뒀으니, 혹시 참고할 일이 있다면 참고해보자.