[java 백준] 골드 5/ 12865번 평범한 배낭

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

12865번: 평범한 배낭

 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
 
    public static int N;
    public static int K;
    public static int W;
    public static int V;
    public static int dp[][];
    public static int weight[];
    public static int value[];
 
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        N=sc.nextInt();
        K=sc.nextInt();
        dp=new int[N+1][K+1];
        weight=new int[N+1];
        value=new int[N+1];
 
        for(int i=1;i<=N;i++){
            weight[i]=sc.nextInt();
            value[i]=sc.nextInt();
        }
 
        for(int i=1;i<=N;i++){
            //이번 차례의 물건을 넣지 않았을 때 또는 이번 차례의 물건을 넣었을 때 둘 중 하나 비교해서 가치판단
           for(int j=1;j<=K;j++){
 
               if(j-weight[i]>=0){
                   dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
               }else{
                   dp[i][j]=dp[i-1][j]; //이전 dp의 값을 저장함.
               }
 
           }
 
        }
        System.out.println(dp[N][K]);
 
 
 
 
    }
}

 

 

문제를 풀면서 중요한 부분

 

이 문제는 냅색문제이고, DP로 풀어볼 것이다. DP 냅색문제의 특징은 물건을 넣었을 때와 넣지 않았을 때 둘 중 더 가치가 큰 것을 선택하는 것이다. 

dp[i][j]는 dp[물건의 개수][물건의 무게] 를 의미한다. 

dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]) 

즉, 현재 물건을 넣었을때 와 넣지 않았을때 중 더 큰 값을 dp[i][j]에 넣어주는 것이다.

여기서 중요한것은 i가 1부터 N까지, j가 1부터 K일때 까지 순회하면서 dp값을 채워가는 것 이였다..!

 

두번째로 중요한 것은 만약 j-weight[i]<0일 때 즉, 버틸 수 있는 무게보다 더 큰 값이 들어왔을 때는

dp[i][j]=dp[i-1][j]로 선언해줘야 했다. 그냥 0으로 냅두는게 아니라 물건을 넣지 않을 때의 값으로 초기화해주는 것이 핵심이다. 그래야 누적합에 오류가 생기지 않는다. 

 

예를 들어 설명해보겠다.

물품의 수가 4이고, 버틸수 있는 무게가 7일 때

무게와 가치를 보면

6 13

4 8

3 6

5 12

가 있다. 

 

dp[2][3]의 경우를 생각해보자.

얘는 3-weight[2]를 하면 3-4=-1이기 때문에  조건에 만족하지 않아서 dp[i][j]=dp[i-1][j] <-- 이 코드가 없었으면 dp[2][3]은 0이 될거다. 근데 직관적으로 생각해보면 문제가 있다. 물건 2개를 가지고 3의 무게를 맞추는 것은 가능하다.무게가 3인애의 가치가 6이기 때문에 dp[2][3]=6이 된다. 

 

어차피 최대 3만큼의 무게를 맞추는게 핵심이지 물건이 꼭 2개만 필요한건 아니기 때문이다. 물건 1개를 가지고 3의 무게를 맞춘다면 그 값또한 dp[2][3]에 해당한다.!! 개수가 기준이 아니라 무게가 기준이여야 했다!!