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

백준 온라인 저지의 12865번 문제인 "평범한 배낭"을 푸는 동적 계획법(Dynamic Programming)을 이용한 풀이입니다.

문제 설명:

문제는 N개의 물건이 주어지고, 각 물건은 무게(weight)와 가치(value)를 갖습니다. 최대 K 무게의 배낭에 물건을 담아 가치의 합을 최대화하는 문제입니다. 각 물건은 하나만 담을 수 있습니다.

알고리즘 및 접근 방법:

이 문제는 0/1 배낭 문제의 전형적인 예시이며, 동적 계획법을 이용하여 효율적으로 해결할 수 있습니다. 코드에서 사용된 접근 방법은 다음과 같습니다.

1. 입력:

• input() 함수는 문제의 입력을 받습니다.
  • N: 물건의 개수
  • K: 배낭의 최대 무게
  • dp[][]: 동적 계획법 테이블. dp[i][j]는 i번째 물건까지 고려했을 때, 무게 j를 넘지 않는 최대 가치를 저장합니다. N+1과 K+1로 크기를 설정하는 이유는 0번째 물건과 0 무게의 경우를 처리하기 위해서입니다.
  • 각 물건의 무게와 가치를 입력받아 dp 테이블을 채우는 반복문이 있습니다.

2. 동적 계획법:

• input() 함수 내부의 이중 반복문이 동적 계획법의 핵심입니다.
  • i: 물건의 인덱스 (1부터 N까지)
  • j: 배낭의 현재 무게 (1부터 K까지)
  • if (j >= weight): 현재 물건의 무게가 배낭의 현재 무게 제한보다 작거나 같다면, 현재 물건을 넣을 수 있습니다.
    • dp[i][j] = Math.max(dp[i-1][j-weight]+value, dp[i-1][j]);: 현재 물건을 넣었을 때의 가치 (dp[i-1][j-weight]+value)와 현재 물건을 넣지 않았을 때의 가치 (dp[i-1][j]) 중 더 큰 값을 dp[i][j]에 저장합니다.
  • else: 현재 물건의 무게가 배낭의 현재 무게 제한보다 크다면, 현재 물건을 넣을 수 없습니다.
    • dp[i][j] = dp[i-1][j];: 이전 물건까지 고려했을 때의 최대 가치를 그대로 사용합니다.

3. 결과 출력:

• result() 함수는 dp[N][K] 값을 출력합니다. dp[N][K]는 모든 물건을 고려했을 때, 최대 무게 K를 넘지 않는 최대 가치를 저장하고 있으므로, 문제의 답이 됩니다.

알고리즘의 특징 및 장단점:

• 장점: 동적 계획법은 0/1 배낭 문제를 효율적으로 해결합니다. 시간 복잡도는 O(NK)로, N과 K가 비교적 작은 경우 효과적입니다. 탐욕적 방법과 달리 최적해를 보장합니다.
• 단점: 공간 복잡도 또한 O(NK)입니다. N과 K가 매우 큰 경우 메모리 제한에 걸릴 수 있습니다. 공간 복잡도를 줄이기 위해서는 1차원 배열을 이용하는 등의 최적화 기법이 필요할 수 있습니다.

코드:

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

public class b12865 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, K;
    static int[][] dp;

    static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        dp = new int[N + 1][K + 1]; // 0번째 행과 열을 고려하여 크기 설정

        for (int i = 1; i <= N; i++) {
            input = br.readLine().split(" ");
            int weight = Integer.parseInt(input[0]);
            int value = Integer.parseInt(input[1]);
            for (int j = 1; j <= K; j++) {
                if (j >= weight) {
                    dp[i][j] = Math.max(dp[i - 1][j - weight] + value, dp[i - 1][j]); // 현재 물건을 넣거나 넣지 않거나 중 최대값 선택
                } else {
                    dp[i][j] = dp[i - 1][j]; // 현재 물건의 무게가 초과하면 이전 결과를 그대로 사용
                }
            }
        }
    }

    static void result() throws IOException {
        bw.write(String.valueOf(dp[N][K]));
    }

    public static void main(String[] args) throws IOException {
        input();
        result();
        bw.flush();
        bw.close();
        br.close();
    }
}