[백준 12865번] 평범한 배낭

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

 

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 = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] dp = new int[K + 1];

        for (int i = 0; i < N; i++) {
            st=new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());

            for (int j = K; j >= W; j--) {
                dp[j] = Math.max(dp[j], dp[j-W] + V);
            }
        }
        System.out.println(dp[K]);

    }
}

 

오늘도 어김없이 DP 문제를 풀었다.

처음에는 백트래킹으로 풀었는데 역시나 시간초과.... 분석을 해본 결과, 물건을 넣을지 안 넣을지를 결정하는 방식으로 탐색해야 했기 때문에, 가능한 모든 경우의 수를 따져야 했다. 이로 인해 시간 복잡도가 O(2^N)으로 증가하게 되었고, N이 100일 경우 2의 100승... 어마 무시하다.

그래서 DP를 활용해서 문제를 해결해야 했다.

배낭 문제(0/1 Knapsack)는 특정 무게 한도 내에서 최대 가치를 얻도록 물건을 선택하는 문제이다. 이를 해결하기 위해 DP 배열을 활용하여 가능한 모든 무게에 대해 최대 가치를 저장하고 갱신하는 방식으로 접근했다.

DP 배열 정의

• dp[i]는 무게 i일 때 얻을 수 있는 최대 가치이다.
• 초기 상태에서 dp[0] = 0이며, 나머지는 0으로 초기화된다.

점화식

• 물건 (W, V)를 넣을지 말지를 결정한다.
• dp[j] = max(dp[j], dp[j - W] + V)
  • 즉, 현재 무게 j에서 해당 물건을 넣을 경우와 넣지 않을 경우 중 더 큰 값을 선택한다.

내림차순 순회의 이유

이때 DP 배열을 갱신할 때, 내림차순으로 순회해야 한다.

오름차순으로 순회하면, 같은 물건을 두 번 이상 사용하는 문제가 발생할 수 있다. 예를 들어, j가 작은 값에서부터 증가하는 방식이라면, 같은 물건을 한 번 넣었을 때 갱신된 값이 이후의 dp[j - W]에서 또 사용될 가능성이 있기 때문이다.

따라서 **내림차순(j = K → W)**으로 순회하면 같은 물건이 중복으로 들어가는 것을 방지할 수 있다. 이렇게 하면 한 번의 반복에서 해당 물건을 고려하고, 그 물건을 한 번만 사용할 수 있는 조건을 유지할 수 있다.