[알고리즘] 백준 - 평범한 배낭

백준 - 평범한 배낭

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class baekjoon_12865 {

    static int N, K;
    static int[] weights;
    static int[] values;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        K = Integer.parseInt(inputs[1]);

        //dp[i][j]는 i번째 물건을 고려했을 때, 무게 K에서 최대 행복
        // dp[i][j] = Max {dp[i-1][j] , dp[i][j-weights[i]] + values[i]}
        // i번째 물건을 안쓰고 그전까지 같은 무게에서 최대 행복 또는
        // i번째 물건을 쓰는대신 i번쨰 물건의 무게만큼 줄어든 것의 최대 행복
        dp = new int[N][K + 1];
        weights = new int[N];
        values = new int[N];
        for (int i = 0; i < N; i++) {
            inputs = br.readLine().split(" ");
            weights[i] = Integer.parseInt(inputs[0]);
            values[i] = Integer.parseInt(inputs[1]);
        }

        for (int i = 0; i < N; i++) {
            for (int j = K; j >= 0 ; j--) {
                if (i - 1 >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
                if (j - weights[i] >= 0) {
                    if (i - 1 >= 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j - weights[i]] + values[i]);
                    }
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - weights[i]] + values[i]);
                }
            }
        }
        
        System.out.println(Arrays.stream(dp[N - 1]).max().getAsInt());

    }
}

처음에는 이중 for문에서 j를 0부터 시작해서 K까지 돌게했다. 그랬더니 에러가 났는데 그 이유는 배낭에는 물건이 하나씩 있는데, 예를 들어 무게 4에 행복 8짜리가 있으면 무게 4일때 8을 만들고 무게 8일때 또 카운팅하여 무게 16을 만들기 때문이다.

또 다른 부분에서 에러가 났는데, 뒤에서부터 카운팅을 하면

4 8
6 13
4 8
4 6
5 12

에 적절히 대응 못한다. 즉 동일한 무게를 가지는 물건이 두 개 있으면 dp[i]j - weights[i]] 는 아직 값이 안정해져 있기 때문에 카운팅을 못하는 것이다. 그래서

  if (i - 1 >= 0) {
      dp[i][j] = Math.max(dp[i][j], dp[i-1][j - weights[i]] + values[i]);
  }

이것을 추가해줬다.