[백준] 12865: 평범한 배낭 JAVA

접근

우선 이 블로그에서 냅색 알고리즘을 공부한 뒤 문제를 풀었다. 자꾸 내 머리로 생각을 안하고 블로그에서 본 점화식을 은연중에 따라하려고 해서 자꾸 답은 안나오는데 이유는 모르겠고 더 헤맸던 것 같다. 아예 작성하던 코드를 버리고 처음부터 내 방식대로(나는 물건 인덱스가 첫 번째 차원에 오는게 더 이해하기 쉬운 것 같다) 풀었더니 금방 성공했다. 

 

여기서 주의할 점은, (현재 수납 가능한 무게) - (넣고자 하는 물건의 무게)가 음수가 될 때의 처리인 것 같다. 나는 처음에 continue만 했기 때문에 최종 결과값이 0이 나오기도 했었다. dp 배열값은 항상 갱신해줘야 함에 유의하자. 

 

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int n, k;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력값 저장
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int[] weights = new int[n];
        int[] values = new int[n];
        
        for(int i = 0;i < n;i++){
            st = new StringTokenizer(br.readLine());
            weights[i] = Integer.parseInt(st.nextToken());
            values[i] = Integer.parseInt(st.nextToken());
        }

        // 냅색 알고리즘
        int answer = solve(weights, values);
        
        // 결과 출력
        System.out.println(answer); 
    }

    static int solve(int[] weights, int[] values){
        int result = 0;
        int[][] dp = new int[n+1][k+1];  // dp[i][j] = i번째 물건까지 넣었을 때, j 무게까지의 최대 가치

        for(int i = 1;i <= n;i++){
            int weight = weights[i-1];
            int value = values[i-1];
            
            for(int j = 1;j <= k;j++){
                if(j < weight) {
                    dp[i][j] = dp[i-1][j];
                    continue;
                }
                
                int curMaxVal = Math.max(dp[i-1][j], dp[i-1][j-weight] + value);
                dp[i][j] = curMaxVal;
                result = Math.max(result, curMaxVal);
            }
        }

        return result;
    }
}