[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)

-내 생각

  이 문제의 경우 혼자 풀어보려고 해서 결과는 잘 나오는 것 같은데 어떤 반례에서 걸리는지 계속 오답처리를 받아서 결국 검색을 해봤는데, 이러한 무게와 가치가 함께 주어지는 문제의 경우 knapsack 알고리즘이라고 별도로 존재한다는 사실을 알 수 있었다. 

 

-해법

  knapsack알고리즘의 경우에 dp 배열을 1차원 또는 2차원으로 해결할 수 있다고 하는데, 많은 사람들이 2차원 배열을 사용하는 것 같다. 나의 경우는 알고리즘 대회를 준비하는 것이 아닌, 취업을 위한 공부이기 때문에 합격선만 만족하면 더 쉬운 것을 사용하는 것이 맞는 것 같다. 

 

  dp배열을 사용할 때 각 인덱스가 의미하는 바는 dp [i번 째 아이템][무게]를 의미한다고 한다. 이를 표로 그려보면 아래와 같이 나타낼 수 있다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item
2번 item
3번 item
4번 item

 

  각 아이템마다 무게를 돌려보는 것으로 볼 수 있는데, 1번 item의 경우 무게, 가치 순으로 (6,13)의 값을 가지므로 이를 표에 표현해보면, 무게가 1 ~ 5일 때는 담을 수 없고, 6부터 담을 수 있기 때문에, 

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item
3번 item
4번 item

  이 된다. 다음으로 2번 item을 담을 경우, 초기 값은 이전 아이템이 각 무게마다 담은 가치들이 그대로 담아질 것이다. dp로 인해 누적해가며 가치를 구해야 하기 때문인데, 2번 item은 (4,8)의 값을 가지므로 무게가 4일 때는 2번을 담을 수 있게 된다. 그렇다면, 1번에서 담은 4번의 가치와 2번의 가치를 비교해 큰 값을 저장하면 되는데, 무게가 6일 경우에는 1번을 담거나 2번을 담을 수 있기 때문에 두 값을 비교해 주어야 한다. 1을 담았을 경우는 이미 이전 행에 값이 존재하기 때문에 구할 필요가 없다. 이를 다시 표로 나타내면, 

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item	0	0	0	8	8	13	13
3번 item
4번 item

  이제 3번 item을 담을 경우, (3,6)이므로 우선 무게가 1, 2인 경우는 이전까지도 담긴 것이 없으므로 그대로 값을 가져온다. 3일 경우는 3번을 담을 수 있으므로 3의 가치가 저장되고, 4일 때는 이전의 4까지 담은 경우와 현재 3번을 담을 경우를 비교해보면 이전의 4까지 담은 경우가 더 크므로 해당 값이 저장된다. 무게가 5일 경우에도 4를 담는 것이 더 크므로 그대로 값이 이어지며, 6일 경우에는 1번 아이템을 담는 것이 가치가 가장 크다. 

 

  이제 무게가 7일 경우가 중요한데, 7일 때 3번 아이템을 담으면 무게가 4만큼이 남게 된다. 무게가 4일 때, 이전 아이템까지 담은 경우의 값이 dp [2][4]에 저장되어 있으므로 3번 아이템의 가치 + 2번 아이템까지 저장된 가치들 중 무게가 4일 때의 가치의 결과가 저장된다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item	0	0	0	8	8	13	13
3번 item	0	0	6	8	8	13	14
4번 item

  마지막으로 4번 아이템의 경우는 (5,12)의 값으로 무게가 1~4일 경우는 모두 이전 아이템까지 구해놓은 가치의 값들을 가지게 된다. 무게가 5일 때부터 자신을 담을 수 있으므로 이전 아이템의 무게 5까지의 가치와 자신의 가치를 비교해 큰 값을 넣는다. 무게가 7일 때, 3번 아이템의 7 무게까지 구해놓은 가치와 자신을 담고 남은 무게를 비교해 큰 값을 넣으면 최종 값을 넣을 수 있다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	0	0	0	0	0	13	13
2번 item	0	0	0	8	8	13	13
3번 item	0	0	6	8	8	13	14
4번 item	0	0	6	8	12	13	14

 

  이를 말로 설명하면 이렇게 어려운데 점화식을 확인해보면 쉬울 것이다. 우선 점화식은 기본적으로 dp[i][j]의 값은 dp [i-1][j]의 값을 가진다. 왜냐하면, 2번 아이템의 경우 무게가 2일 때까지 2번 아이템은 저장하지 못하므로, 1번 아이템에서 구해놓은 가치를 저장해둔다.

 

  이제 무게가 3일 때는 2번 아이템을 담을 수 있기 때문에 고려해야 할 것이 하나 늘어나게 된다. 앞선 점화식으로 구한 가치와 자신의 무게를 뺐을 때 남은 무게로 담을 수 있는 가치를 자신의 가치와 더해 비교해야 한다. 이를 점화식으로 표현하면 dp [i][j] = dp [i-1][j - w [i]] + v [i]가 된다. 즉 무게가 6일 때, 1번 아이템에서 구한 가치가 13이고, 자신을 담을 때 남는 무게는 6-3으로 3이 된다. 그렇다면 3의 무게를 더 담을 수 있으므로 1번 아이템에서 무게가 3일 때 구해놓은 가치와 자신의 가치를 합치면 된다. (이는 물건들을 한 번 담았을 때 다시 담을 수 없는 문제의 특성으로 인해 이런 식으로 진행된다. 만약 반대로 담았던 물건을 다시 담을 수 있는 상황의 경우 2번 아이템을 2번 담으면 16이 되므로 16과 13을 비교한다.) 그러나 무게가 3일 때 1번 아이템은 담을 수 있는 물건이 존재하지 않으므로 자신의 가치인 8과 13을 비교해 더 큰 가치인 13을 담게 된다.

 

  코드는 간결하다. 

 

import java.util.*;

public class Main {
	static int n,k;
	static int dp[][],w[],v[]; // dp배열과 무게, 가치배열
	
	
	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];
		
		w =new int[n+1];
		v = new int[n+1];
		
		for(int i=1;i<=n;i++) {			
			w[i] = sc.nextInt();
			v[i]= sc.nextInt();
		
		}
		
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=k;j++) {
				dp[i][j] = dp[i-1][j]; // 기본적으로 이전 아이템의 가치를 저장한다.
				if(j - w[i]>=0) { // 무게에서 자신의 무게를 뺐을 때 남는 무게가 존재하면,
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); // 이전 아이템에서 구한 가치와 남은 무게의 가치 + 자신의 가치 중 큰 값을 취한다.
				}
			}
		}
		
		System.out.println(dp[n][k]);
		
		
		
	}
	
}

---

  이전 풀이를 안보고 풀어서 물품의 무게와 가치를 1차원 배열로 별도로 저장한 것이 아닌, 2차원 배열로 저장해 속도면에서는 느린 결과가 나타나기도 했지만 어찌 됐든 통과되기는 한다. 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		// 물품의 수 
		int n = in.nextInt();
		
		// 버틸 수 있는 무게
		int k = in.nextInt();
		
		// 물품의 무게(0)와 가치(1)
		int a[][] = new int[n+1][2];
		
		// 행: 물품의 무게, 열: 1~k까지의 무게, 값: 물품의 가치 누적
		int dp[][] = new int[n+1][k+1];
		
		// 물품들의 무게와 가치 입력
		for(int i=1;i<n+1;i++) {
			a[i][0] = in.nextInt();
			a[i][1] = in.nextInt();
		}
		
        // 0행, 0열은 공백 인덱스로 비워둔다.
		for(int i=1;i<n+1;i++) {
			for(int j=1;j<k+1;j++) {
            	// 비교 무게 - 물품의 무게 >= 0 인 경우,
				if(j - a[i][0] >= 0) {
                	// 이전 dp에 저장된 누적 가치와 자신의 가치+남은 무게의 가치 중 큰 값을 취한다.
					dp[i][j] = Math.max( dp[i-1][j], a[i][1]+dp[i-1][j-a[i][0]]);
				}else {
                	// 나머지는 이전 dp에 누적된 가치를 취한다.
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		
		System.out.println(dp[n][k]);
				
		in.close();
	}

}