[백준] 12865 - 평범한 배낭(Java)

문제 파악

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

풀이

DP 문제의 정석으로 보인다.. 항상 어떤 데이터를 중점으로 배열을 구성할 지 정하도록 하자.

문제에서 주어진 데이터는 가방의 개수 N, 무게 W, 가치 V이다.
그 중 변동이 적어 보이는 무게 W를 기준으로 잡아 최대 가치 V를 구하는 방향을 택하였다.
그러기 위해 배열 DP[W]를 선언해 주도록 한다.

이 문제는 입력을 받으며 DP 배열을 업데이트 해 주었다.

새로운 물건에 대한 입력(wVal - 무게, vVal - 가치) 을 받을 때

• wVal : 만일 기존의 DP[wVal] 보다 높다면 업데이트
• wVal + 1 ~ maxWeight : DP[maxWeight-wVal] + vVal, DP[maxWeight-wVal]와 비교하여 업데이트
  • 이 때, 연산 중복을 막기 위해 maxWeight 부터 역순으로 계산

시간 복잡도 : O(N*W), 공간 복잡도 : O(W)

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        int count = scan.nextInt();
        int weight = scan.nextInt();
        int[] dp = new int[weight + 1];
        for (int i = 0; i < count; i++) {
            int wVal = scan.nextInt();
            int vVal = scan.nextInt();
            if (wVal > weight) {
                continue;
            }
            for (int w = weight; w >= wVal; w--) {
                dp[w] = Math.max(dp[w], dp[w - wVal] + vVal);
            }
        }
        scan.close();
        int answer = 0;
        for (int w = 0; w <= weight; w++) {
            answer = Math.max(answer, dp[w]);
        }
        System.out.println(answer);
    }
}