[BOJ] 12865:평범한 배낭

0. 문제

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

12865번: 평범한 배낭

 

 

1. 문제분석

-  기존의 상태(기존에 배낭에 넣은 다른 물건들로 인해 결정된 무게)에 대해서 기존의 상태를 바꿀 수 있는 경우의 수(기존 배낭에 새로운 물건을 넣는 것) 중, 그 최댓값을 찾는다는 점에서 Dynamic Programming을 사용해 문제를 풀어야 함을 알 수 있다.

- dp[n][w] : n번째 물건까지 배낭에 넣거나 넣지 않았을 때,  w 무게 이하에서 얻을 수 있는 최대의 가치 

2. 주의할 점

- 단순히 무게만 생각하다보면 무게 조건만 만족하는 코드(각 물건은 한 개씩만 가방에 들어갈 수 있다는 조건을 무시하게 된다든지)를 짜게된다. 하지만 문제의 조건은 "각 물건은 하나씩만 존재하고, 반복해서 넣을 수 없음"임을 명심하자.

- 조건을 잘 읽어야 한다. 문제에서 최대 K 무게까지의 배낭을 들 수 있다고 했으므로, 단순히 배낭에 넣은 물건 무게의 합이 정확하게 K 무게일 경우가 아니라 무게의 최댓값이 K인 경우, 즉 실제 무게는 K 이하인 경우를 모두 고려해서 dp 값을 구해야 한다. 

- 어떤 물건을 몇 번째로 넣느냐는 전혀 상관없다. 따라서 물건을 어떤 순서로 넣든 간에 순차적으로 N개의 모든 물건에 대한 경우의 수를 한번씩 고려해야 한다. 

3. 소스코드(Java)

// boj 12865 평범한 배낭
// Dynamic Programming
// Knapsack Algorithm


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

public class boj_12865 {

    private static int N;
    private static int K;
    private static int[] W;
    private static int[] V;
    private static int[][] dp;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        K = stoi(st.nextToken());
        W = new int [N];
        V = new int [N];
        // dp[n][w] : 0번부터 n번째 물건까지 검사했을 때, w의 무게 이하에서 얻을 수 있는 최대 가치
        dp = new int[N][K + 1];
        for (int i = 0; i < N; ++i) {
            st = new StringTokenizer((br.readLine()));
            W[i] = stoi(st.nextToken());
            V[i] = stoi(st.nextToken());
        }
        for (int w = 0; w <= K; ++w) if (W[0] <= w) dp[0][w] = V[0];
        for (int n = 1; n < N; ++n) {
            for (int w = 0; w <= K; ++w) {
                // 현재의 상태(dp[n-1][w-W[n]])에 현재의 물건(W[n])을 추가로 넣을 수 있는지
                if (W[n] <= w) dp[n][w] = Math.max(
                        dp[n - 1][w], dp[n - 1][w - W[n]] + V[n]);
                else dp[n][w] = dp[n-1][w];
            }
        }
        System.out.print(dp[N - 1][K]);
    }

    private static int stoi(String s) {
        return Integer.parseInt(s);
    }

}

4. 여담

- 오랜만의 문제풀이라 시간이 꽤 오래 걸렸다.. 빨리 풀 수 있을 줄 알았는데...

- 너무 모든 문제를 visited 배열을 써서 풀려고 생각하지는 말아야겠다. 모든 경우의 수를 방문하는 것은 미련한 짓일지도.