[JAVA/DP] 백준 12865 평범한 배낭

1. 문제

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

12865번: 평범한 배낭

 

2. 풀이

• DP를 이용해 풀이한다.
• 2차원 배열로 DP를 진행한다. 
  • 첫번째 인덱스는 무게를 의미한다. dp[k][n]일 경우, k 무게 만큼 버티고 있을 때다.
  • 두번째 인덱스는 물품의 인덱스를 의미한다. dp[k][n]일 경우, n번째 물건까지를 고려했을 때다.
• 즉, DP 배열에 저장되는 값은 인덱스에 해당하는 물건들의 가치합의 최댓값이다. 만약 dp[k][n]의 경우 (1) k 무게 까지 버틴 경우, (2) n번째 인덱스의 물품까지 고려했을 때의 가치의 최댓값이다.
• max 함수를 사용해, dp 배열에 물건들의 가치합의 최댓값이 계속해서 저장되도록 한다.

 

3. 코드

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

// DP

public class Main {
    public static void main(String[] args) throws Exception {
        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[][] arr = new int[n+1][2];
        int[][] dp = new int[k+1][n+1]; 
        
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); // 무게
            arr[i][1] = Integer.parseInt(st.nextToken()); // 가치
        }
        
        for(int i = 1; i <= k; i++) {
            for(int j = 1; j <= n; j++) {
                if(i - arr[j][0] >= 0) { // 가방에 넣을 수 있는 경우
                    dp[i][j] = Math.max(dp[i][j], dp[i - arr[j][0]][j-1] + arr[j][1]);
                }
                dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
            }
        }
        
        System.out.println(dp[k][n]);
    }
}