[JAVA] 백준 12865번 - 평범한 배낭

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();
		int knapsack[][] = new int[N+1][2];
		int dp[][] = new int[N+1][100001];
		
		for (int i = 1; i <= N; i++) {
			knapsack[i][0] = sc.nextInt();
			knapsack[i][1] = sc.nextInt();
		}
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				int w = knapsack[i][0]; // 현재 아이템의 무게
				int v = knapsack[i][1]; // 현재 아이템의 가치
				if(j-w >= 0) {
					dp[i][j] = Math.max(dp[i-1][j-w]+v, dp[i-1][j]);
				}else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		
		
//		for (int i = 1; i <= N; i++) {
//			for (int j = 1; j <= K; j++) {
//				System.out.print(dp[i][j]+" ");
//			}
//			System.out.println();
//		}
		
		System.out.println(dp[N][K]);
		
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

이러한 문제를 처음 접하신다면 굉장히 어려울 수 있는 문제라고 생각합니다. 저도 이 문제를 처음 접했을 때 하루 종일 고민하다가 답을 못 찾고 검색을 한 기억이 있네요... 반복해서 풀다 보니 어떻게 접근을 해야 할지 감각적으로 알게 되는 것 같습니다.

 

dp 문제를 풀이할 때는 dp의 정의부터 세우는 것이 가장 중요한 것 같습니다.

dp[i][j] : j까지 버틸 수 있는 배낭에 1~i번째 물건들만 사용해서 만들 수 있는 가치의 최댓값

ex) dp[2][6] : 배낭이 버틸 수 있는 무게가 6이고 1번, 2번 물건만 사용해서 만들 수 있는 가치의 최댓값

 

 

for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= K; j++) {
		int w = knapsack[i][0]; // 현재 아이템의 무게
		int v = knapsack[i][1]; // 현재 아이템의 가치
		if(j-w >= 0) {
			dp[i][j] = Math.max(dp[i-1][j-w]+v, dp[i-1][j]);
		}else {
			dp[i][j] = dp[i-1][j];
		}
	}
}

d[3][7]의 경우를 예시로 들자면 dp[3][7]에서 3번 물건을 넣느냐 아니면 넣지 않느냐로 나뉠 수 있습니다.

3번 물건의 무게 w = 3
3번 물건의 가치 v = 6

1. 3번 물건을 넣는다.

3번 물건을 넣을 경우 배낭에는 w만큼의 공간이 필요하게 됩니다. 현재 배낭이 버틸 수 있는 최대 무게는 7이고 w만큼 공간이 필요하기 때문에 dp[3][7] = dp[2][4] + v = 8 + 6 = 14가 됩니다.

2. 3번 물건을 넣지 않는다.

3번 물건을 넣지 않는다고 하면 자동적으로 dp[3][7] = dp[2][7]이 됩니다.

 

이렇게 하여 최종적으로 dp[N][K]값을 구할 수 있게 됩니다.

dp[N][K] : K만큼 버틸 수 있는 배낭에 1~N번 물건을 사용해서 만들 수 있는 가치의 최댓값

 

🔗 링크

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

12865번: 평범한 배낭