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

문제 링크 : https://www.acmicpc.net/problem/12865

이 문제는 DP를 이용하여 풀 수 있습니다. DP 배열을 다음과 같이 설정합니다.

DP[N][K] : N번 아이템까지 K 무게만큼 배낭에 넣었을 때 가치의 최댓값

이후 점화식을 생성합니다.

우선 기본적으로 i번 아이템까지 넣을 때의 가치의 최댓값은 i-1번 아이템까지 넣었을 때의 가치의 최댓값보다 크게 됩니다. 왜냐하면 현재 아이템을 넣기 전의 최댓값을 그대로 가지고 가기 떄문이죠.

그럼 여기서 현재 아이템을 추가할 때의 최댓값 계산을 진행해주시면 됩니다. 즉 i-1번 아이템까지 넣은 최댓값에 현재 아이템의 가치를 추가한 값과 현재 상태와의 최댓값을 계산합니다.

아래는 코드입니다.

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

class Main{
    static int N,K;
    static long[][] dp;
    static int[][] item;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        item = new int[N+1][2];
        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            item[i][0] = w;
            item[i][1] = v;
        }

        dp = new long[N+1][K+1];
        for(int k=1;k<=K;k++){
            for(int n=1;n<=N;n++){
                dp[n][k] = dp[n-1][k];
                if(k >= item[n][0]){
                    dp[n][k] = Math.max(dp[n][k], dp[n-1][k - item[n][0]]+item[n][1]);
                }
            }
        }
        System.out.println(dp[N][K]);
    }
}