[백준알고리즘-JAVA]12865번 풀이(평범한 배낭) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 12865번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 12865 (평범한 배낭)

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

 

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

 

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

 

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 출력한다.

입력 예시

4 7
6 13
4 8
3 6
5 12

출력 예시

14

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int[][] arr;
	static int[][] dp;
	static int N;
	static int weight;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		weight = Integer.parseInt(st.nextToken());
		
		
		arr = new int[N+1][2];
		dp = new int[N+1][weight+1];
		
		for(int i = 1 ; i <= N ;i ++) {
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st1.nextToken());
			arr[i][1] = Integer.parseInt(st1.nextToken());
		}
		
		for(int i = 1 ; i <= N ; i++) {
			for(int j = 1 ; j <= weight ; j++) {
				if(j - arr[i][0] >= 0)
					dp[i][j] = Math.max( dp[i-1][j], arr[i][1]+dp[i-1][j-arr[i][0]]);
				else 
					dp[i][j] = dp[i-1][j];
			}
		}
		
		System.out.println(dp[N][weight]);
}

}

 평범한 배낭 문제는 dp문제의 대표적인 문제입니다. 이번 문제에서도 역시나 핵심은 dp를 무엇으로 설정하느냐! 이것이 핵심이라고 생각합니다.

 

 이번 dp에 담을 내용은 바로 가치의 최댓값입니다. 이점을 항상 기억해야 합니다. 이전 글에서 말했듯이 dp에 담아야 하는 내용은 언제나 답이 포함되어있어야 합니다.

 

STEP을 따라가며 이해 보도록 하죠

---

알고리즘 흐름도

입력받기 -> 규칙 찾기 -> 재귀 OR 반복문 활용하여 DP 채우기 -> 출력하기

---

STEP1 DP를 이용하여 규칙 찾아보기

 가장 어려운 STEP1!! 그러나 이것만 이해한다면 나머지 STEP은 쉬운 단계입니다. 한번 가보도록 합시다

 

저희가 찾아야 하는 값은 일정 무게를 넘지 않는 최대치의 가치를 차아야 합니다. 일단 주어진 값을 표로 표현하여 봅시다.

	6	4	3	5
13
8
6
12

열 부분은 ITEM의 무게를 의미하고 행 부분은 그 가치를 의미하게 되죠 그러나 이런 식의 접근은 표를 채우기부터가 힘듭니다. 왜냐하면 의미가 정확하지 않기 때문이죠. 특히 행 부분의 값들은 딱히 이 표에 쓸모 있는 정보가 아니기 때문이죠.

 

이를 좀 더 개편하여 아래의 표와 같이 표현하여 봅시다.

	0	1	2	3	4	5	6	7
13 - 6
8 - 4
6 - 3
12 - 5

각 열은 사용자가 들 수 있는 최대 무게까지의 무게들을 표현한 것이고 각 행은 각 아이템의 무게와 가치를 표현한 표입니다.  이제 이 표를 활용하여 한번 채워보도록 하죠. 가장 먼저 13의 가치를 가지고 있고 6의 무게인 것부터 시작해 보겠습니다.

 

	0	1	2	3	4	5	6	7
13 - 6	0	0	0	0	0	0	13	13
8 - 4
6 - 3
12 - 5

간단하죠 0 ~ 5의 무게에는 6의 무게를 담을 수 없고 6과 7에 해당 값이 들어갑니다.

(여기서 중요한 점은 아직 4와 3과 5의 무게를 가진 아이템을 고려하지 않았다는 점!)

 

다음 단계는 이제 4의 무게를 가진 아이템을 포함하여 포를 채워보죠

	0	1	2	3	4	5	6	7
13 - 6	0	0	0	0	0	0	13	13
8 - 4	0	0	0	0	8	8	13	13
6 - 3
12 - 5

앞에서 채웠든 1행 부분은 그대로 내버려 두고 2번째 행으로 갑니다. 이때는 4부터 8의 가치를 가질 수 있죠. 그러나 6이 되는 순간 6의 무게를 가진 아이템을 넣을 수 있게 됩니다. 그렇게 되면 가치는 13이 최댓값이 되겠죠 이런 식으로 쭉 채워 줍니다.

 

	0	1	2	3	4	5	6	7
13 - 6	0	0	0	0	0	0	13	13
8 - 4	0	0	0	0	8	8	13	13
6 - 3	0	0	0	6	8	8	13	14
12 - 5	0	0	0	6	8	12	13	14

여기서 우리는 규칙을 찾아야 합니다. 일단 우리는 1가지는 쉽게 알아낼 수 있죠

 

 - 각 열의 무게에서 자신의 무게를 뺀 값이 0 이상이라면 나의 가치가 들어간다!!!

여기사 하나의 예외를 고려해줘야 합니다. 만약에 0 미만이라면???

 

무슨 값이 들어가야 할까요??

 

그런 상황이 어디에 나와있을까요? 바로 4번째 열의 3의 무게를 가리키는 곳을 봐야 합니다. (4, 4)

 

이 값은 3의 무게를 넣을 수 있는데 넣을 아이템이 5입니다. 그러나 가치가 6으로 표현되어있죠. 이 말은 즉 그전에 3의 무게를 가진 아이템이 들어갈 수 있기 때문입니다.

(그 이전의 행에 들어가지 않은 이유는 앞에서 말했듯 우리는 첫 행부터 시작하며 아래행을 고려하지 않고 채워나갔죠)

즉 예외 상황에서는 바로 자신의 윗행의 값을 가져오면 끝!

 

그러나 여기서 큰 예외는 처리하였지만 가장 중요한 한 가지를 더고려해 줘야 합니다.

 

앞서 찾은

 - 각 열의 무게에서 자신의 무게를 뺀 값이 0 이상이라면 나의 가치가 들어간다!!!

이런 규칙에서 하나를 추가해야 하는 것이죠

 

3의 무게와 4의 무게가 더해져서 7의 무게가 되는 것처럼 이런 예외상황을 처리해 줘야 합니다. 이러한 상황을 처리하기 위해서 고민해봐야 합니다.

 

이는 아래 STEP을 통해 코드를 통해 이해하는 것이 쉬움으로 다음 STEP에 가서 이해해봅시다!

---

STEP2 반복문 구현하기

for(int i = 1 ; i <= N ; i++) {
			for(int j = 1 ; j <= weight ; j++) {
				if(j - arr[i][0] >= 0)
					dp[i][j] = Math.max( dp[i-1][j], arr[i][1]+dp[i-1][j-arr[i][0]]);
				else 
					dp[i][j] = dp[i-1][j];
			}
		}

여기서는 DP의 핵심문장에 대한 설명을 하겠습니다. 

 

dp[i][j] = Math.max( dp[i-1][j], arr[i][1]+dp[i-1][j-arr[i][0]]);

바로 이문장을 잘 이해해야 합니다.

 

dp [i-1][j]가 의미하는 것

자신의 위 즉, 이전 아이템에서 가질 수 있는 최대의 가치입니다.

 

arr [i][1]가 의미하는 것

 자신의 가치를 의미합니다.

 

dp [i][j-arr [i][0]]이 의미하는 것

현재 무게에서 자신의 무게를 뺀 곳의 최대 가치를 의미합니다.

즉, 예를 들어 3번째 열에 집중을 해봅시다. 마지막 7의 무게를 사용할 때 j는 7의 값을 가지고 있고 arr [3][0]은 3을 가지고 있죠. 그렇다면 4로 가게 됩니다. 여기서 4로 가게 된 곳의 dp는 무엇을 의미할까요??

 

바로 들 수 있는 무게의 최대가 4일 때 가질 수 있는 최대의 가치입니다. (마지막 5의 무게를 가진 아이템을 고려하지 않은)

바로 4의 무게를 가지는 가치와 자신의 가치를 더한 값과 |||| 자신 이전 아이템에서 가질 수 있는 최대의 가치를 비교합니다.

 

이를 쉽게 한국말로 풀이해 보면

 

이전 아이템이 가질 수 있는 최댓값 vs 자신의 값 + 최대 무게가 넘어가지 않는 다른 물건을 합친 가치

 

이런 식으로 표현이 되게 되죠.

 

사실 저도 이것을 말로 표현하려니 굉장히 어렵네요 ㅜㅜㅜ

 

이해가 잘 되셨을지 잘 모르겠네요....

 

해답을 봐서 이해하기도 힘든데, 이를 아무것도 모르는 상태에서 풀어보려 한다면, 굉장히 어려운 문제였다라고 생각합니다...

---

dp1 문제 모음을 마치면서 동적 계획법에 대해서 간략히 생각을 정리하면 다음과 같다고 할 수 있습니다.

 - 처음 접하면 굉장히 어렵다.

 - dp에 무엇을 어떻게 담을지 고려해야 한다.

 - 항상 채워 넣을 때는 채워 넣을 인덱스까지만 고려해서 채워 넣자

 - 해설을 봐도 헷갈리는 게 있으면, 그냥 여러 번 풀어보자 (이해가 어려우면 익숙해지고 이해하자)

 

항상 어려운 문제들은 있기 마련입니다. 여기서 포기하지 마시고 그냥 그 해설이 익숙해질 때까지 똑같이 풀어보세요. 어느 정도 익숙해졌다면, 이제 이해를 하고 같은 유형의 다른 문제를 풀어보세요!!