[백준] 12865번 : 평범한 배낭 (DP)

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

풀이

이 문제는 0/1 배낭 문제(0/1 Knapsack Problem)로, 동적 계획법(DP, Dynamic Programming)을 사용해 해결할 수 있습니다. 각 물건에 대해 선택할지 말지를 결정하여 배낭의 최대 가치를 계산하는 문제입니다.

문제 분석

• 문제 설명:
  • N개의 물건이 있고, 각 물건에는 무게 W와 가치 V가 있습니다.
  • 최대 무게 K까지의 배낭에 물건들을 담을 수 있으며, 가치의 합이 최대가 되도록 물건을 고르는 것이 목표입니다.
  • 각 물건은 한 번만 선택할 수 있으며, 선택하지 않을 수도 있습니다.

해결 전략

이 문제는 동적 계획법(DP)을 사용하여 해결합니다. DP 테이블을 이용해 최대 가치를 누적 계산하면서 최적의 선택을 찾습니다.

1. DP 테이블 정의:
   • dp[i][w]는 i번째 물건까지 고려했을 때, 배낭의 무게가 w일 때의 최대 가치를 의미합니다.
2. 점화식:
   • dp[i][w] = max(dp[i-1][w], dp[i-1][w-W] + V)
     • dp[i-1][w]: i번째 물건을 선택하지 않는 경우.
     • dp[i-1][w-W] + V: i번째 물건을 선택하는 경우(이전 배낭 무게에서 현재 물건의 무게 W를 뺀 상태에서의 최대 가치에 현재 물건의 가치를 더한 값).
3. 기본 아이디어:
   • 각 물건에 대해 선택 여부를 결정할 때, 현재 배낭의 무게에 맞춰 선택할지 말지를 결정합니다.
   • 중복 계산을 방지하기 위해 이전 결과를 저장하며 문제를 풀어나갑니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        
        int N = Integer.parseInt(inputs[0]);
        int K = Integer.parseInt(inputs[1]);
        
        int[][] item = new int[N+1][2];
        
        for (int i = 1; i <= N; i++) {
            inputs = br.readLine().split(" ");
            item[i][0] = Integer.parseInt(inputs[0]);  // 무게 W
            item[i][1] = Integer.parseInt(inputs[1]);  // 가치 V
        }
        
        // DP 테이블 선언 (0으로 초기화)
        int[][] dp = new int[N+1][K+1];
        
        for (int i = 1; i <= N; i++) {
            for (int k = 0; k <= K; k++) {
                dp[i][k] = dp[i-1][k];  // i번째 물건을 선택하지 않은 경우
                if (k - item[i][0] >= 0) {  // i번째 물건을 선택할 수 있는 경우
                    dp[i][k] = Math.max(dp[i][k], dp[i-1][k-item[i][0]] + item[i][1]);
                }
            }
        }
        
        // 배낭에 담을 수 있는 최대 가치 출력
        System.out.println(dp[N][K]);
    }
}

코드 설명

1. 입력 처리:
   • N은 물건의 수, K는 배낭이 버틸 수 있는 최대 무게.
   • W[i]는 각 물건의 무게, V[i]는 각 물건의 가치를 나타냅니다.
2. DP 테이블 초기화:
   • dp[i][j]는 i번째 물건까지 고려했을 때, 배낭의 최대 무게가 j일 때 가질 수 있는 최대 가치를 저장합니다.
3. 동적 계획법(DP) 점화식:
   • i번째 물건을 선택할지 여부에 따라 값을 갱신합니다.
   • 만약 현재 무게 j가 i번째 물건의 무게보다 크거나 같다면, 그 물건을 선택할 수 있습니다.
   • 이때, dp[i][j]는 이전 단계에서 물건을 선택하지 않았을 때의 값(dp[i-1][j])과, 선택했을 때의 값(dp[i-1][j-W[i]] + V[i]) 중 큰 값을 선택합니다.
   • 물건을 선택할 수 없다면, 이전 값을 그대로 가져옵니다(dp[i-1][j]).
4. 최종 결과:
   • 모든 물건을 고려한 후 배낭 무게가 K일 때의 최대 가치를 출력합니다(dp[N][K]).

시간 복잡도

• 시간 복잡도: O(N * K)
  • N은 물건의 수, K는 배낭의 최대 무게.
  • DP 테이블을 채우는 데에는 N개의 물건을 하나씩 고려하고, 각 물건에 대해 배낭의 무게 K까지 반복하면서 값을 갱신하므로, 전체 시간 복잡도는 O(N * K)입니다.
• 공간 복잡도: O(N * K)
  • DP 테이블은 N개의 물건과 K개의 무게를 기준으로 저장되므로, 공간 복잡도는 O(N * K)입니다.