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

접근

DP 알고리즘 다시 봐야지! 하면 항상 냅색 문제부터 먼저 풀었더니 결국 감이 없는 상태에서 솔루션 참고하고 내 힘으로 풀었던 적은 없는 것 같다. 그래서 이번에는 쉬운 dp 문제들로 먼저 빌드업을 하고왔다 ㅎ 처음에 dp가 어려웠던 이유는 자꾸 그리디처럼 접근해서 그랬던 것 같다. 그냥 이전의 결과를 활용해서 하나씩 새로운 값을 누적하여 계산하면 된다.

 

짐을 쌀 때 (1) 물건을 포함하는 경우 (2) 물건을 포함하지 않는 경우 2가지로 나뉘기 때문에, 특정 무게일 때 두 가지 경우 중 더 높은 가치를 가지는 값을 저장하면 된다. 즉 무게는 1부터 k의 최대값(100,000)까지 반복하며, 모든 물건별로 넣고 안넣고를 비교해준다. 이 때 dp[i-1][]을 참조해야 하므로 배열의 크기를 n+1로 잡아줬다.

 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] weight = new int[n+1];
        int[] value = new int[n+1];
        int[][] dp = new int[n+1][k+1];

        for(int i = 1;i <= n;i++){
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= k;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]] + value[i]); 
            }
        }

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