(JAVA)백준 문제 풀이 - 동적계획법 단계 - 12865번 평범한 배낭 (골드 5)

이번 문제는 동적 프로그래밍을 이용하여 배낭에 넣을 수 있는 최대 가치 값을 찾아내는 문제이다.

골드 난이도 답게 난도가 좀 있었는데 혼자서 이리저리 짜보다가 생각처럼 잘 되지 않아 ChatGpt의 도움을 약간 받아 해결하였다.

그러면 어떻게 문제를 풀었고 어디가 문제였는지 살펴보자.

---

무엇이 반복되는가?

이전 글에서도 서술 했지만 동적 계획법의 핵심은 반복되는 요소를 기록하여 시간을 단축시키는 것이다.

그러면 무엇이 반복되는 것이고 그것을 어떤 방법으로 기록할 것인지가 핵심이 되겠다.

문제는 배낭의 넣을 수 있는 물건들의 최대 가치값만을 요구하고 있기 때문에 안에 몇개가 들어가는지, 몇종류가 들어가는지는 중요하지 않다.

즉, 배낭에 무게별로 들어가는 가치합이 반복되는 요소가 될 것이다.

그럼 남은 문제는 무게별 가치값을 어떻게 계산하고 어떻게 저장할 것인지가 되는데 여기서에서 꽤 애를 많이 먹었다.

처음에 생각해 낸 방법은 무게+1만큼 1차원 배열을 만들고 각 물품의 무게를 배열의 초기 값으로 선언하였다.

도식화 하면 다음과 같이 될 것이다.

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

그런 후 최종 무게값을 던져서 값이 있으면 리턴하고 없으면 2중 for문을 이용하여 던진 무게의 가치값을 계산하는 Top-Down 방식으로 생각을 하고 구성하였는데 생각처럼 잘 되지 않았다.

우선, 지금처럼 값이 간단할때야 문제가 없다.

그런데 만일 다음과 같이 문제가 주어진다고 생각해보자

0	1	2	3	4	5	6	7	8
	2	4			2

위의 예제에서 최종 값은 8이 되어야 한다.

하지만 실제로 Top-Down 방식으로 진행시에 각 인덱스의 값을 확인을 위하여 Math.max를 이용하여 비교하도록 만들었더니 다음과 같이 테이블이 구성되었다.

0	1	2	3	4	5	6	7	8
	2	4	6	8	10	12	14	16

실제 나와야 할 값이 아닌 모든 조합의 최대 합으로만 계산이 되니 정상적으로 출력이 되질 않았다.

결과적으로 중간에 초기값이 있는 경우 해당 초기값을 불러오도록 바꿔야 했는데 이게 감이 잘 오질 않았다.

(물론 내가 로직을 잘 못 구성한 것일수도 있다.)

2차원 배열로 만들어야 한다는 것은 알겠는데 Memoization을 어떻게 해야할지 모르겠달까...

그래서 ChatGPT에게 도움을 구해보았다.

---

도와줘요 ChatGPT!

가방의 용량(Capacity)이 10이고, 다음과 같은 물건 목록이 주어집니다. 각 물건은 무게와 가치를 가지고 있습니다.

물건 1: 무게 2, 가치 5 물건 2: 무게 3, 가치 7 물건 3: 무게 4, 가치 3 물건 4: 무게 5, 가치 2

이 문제를 풀 때 다음과 같은 단계를 따를 수 있습니다.

1. 2차원 배열을 만듭니다. 표의 각 셀은 무게 및 물건의 조합에 대한 최대 가치를 저장하는데 사용됩니다. 초기에는 0으로 초기화됩니다.
2. 각 물건에 대해 냅색 테이블을 업데이트합니다. 물건을 하나씩 고려하면서 다음과 같은 규칙을 따릅니다:
   • 만약 물건의 무게가 현재 고려 중인 무게 제한을 초과하면, 이 물건을 선택할 수 없으므로, 이전 행의 값(같은 무게에서의 최대 가치)을 복사합니다.
   • 물건의 무게가 무게 제한을 초과하지 않는 경우, 이 물건을 선택할 수 있습니다. 이 경우, 이전 행의 동일한 무게에서의 최대 가치와 현재 물건의 가치를 더해 업데이트합니다.
3. 표의 마지막 행과 마지막 열에는 최적해가 저장됩니다. 이 값은 우리가 원하는 답, 즉 가방에 넣을 수 있는 물건의 최대 가치를 나타냅니다.

결과적으로 2차원 배열을 만드는 것은 맞았다.

int arr[] = new int[물건의 갯수][무게];

위와 같이 조합의 수와 무게만큼 2차원 배열을 만들고 해당 테이블을 업데이트 하는것이 핵심이였는데, 이렇게 되면 각 무게에서는 해당 무게를 가진 초기값이 저장되므로 모든 테이블을 채운 후 마지막 행,열만 가져오면 문제를 해결 할 수 있었다.

위 테이블은 전체적으로 보면 모든 경우에 수에 대한 가치값을 기록한 것과 같은데 각 무게를 채워 나갈때 이전행의 데이터와 비교해 나가면서 전체 데이터를 채우게 되는 것이다.

자세한 방법은 문제를 다 풀고 나서 블로그를 찾아보다가 너무 잘 정리 된 글이 있어 소개하니 이쪽을 참고하기 바란다.

 

참고자료

https://st-lab.tistory.com/141

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

---

이제 풀어보자!

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

class Main{
    public static int n,k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        Item[] arr = new Item[n];

        for (int i = 0; i < n; i++) {
            str = br.readLine().split(" ");
            arr[i] = new Item(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
        }

        System.out.println(findn(arr,k));

    }

    public static int findn(Item[] items, int c) {
        int l = items.length;
        int[][] dp = new int[n + 1][c + 1];

        for (int i = 1; i <= l; i++) {
            for (int j = 1; j <= c; j++) {
                if (items[i-1].w > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - items[i - 1].w] + items[i - 1].v);
                }
            }
        }

        return dp[n][c];
    }

    public static class Item{
        int w;
        int v;

        public Item(int w, int v) {
            this.w = w;
            this.v = v;
        }

    }
}

결론적으로 나는 Bottom-Up 방식으로 최종 구현을 마쳤는데 Iten 클래스를 구성하여 각 물품을 배열로 저장한다.

그 후, 최종 무게와 해당 배열을 던져서 테이블을 채워 나가는데, 이 때에 중심이 되는 부분은 이곳이다.

for (int i = 1; i <= l; i++) {
            for (int j = 1; j <= c; j++) {
            //현재 물건을 선택할 수 없는 경우
                if (items[i-1].w > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                //현재 물건을 선택할 수 있는 경우 더 큰 값을 선택
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - items[i - 1].w] + items[i - 1].v);
                }
            }
        }

items의 인덱스를 맞추기 위하여 해당 물품인 경우 -1을 해주었고, 각 케이스 마다 비교하여 물건을 선택할 수 없는 경우 이전 행의 같은 컬럼 값을 가져오고, 선택할 수 있는 경우 현재 무게(j) - 현재 물건의 무게 (items[i-1].w)의 값과 현재 물건의 값(items[i-1].v)를 더한 값과 이전 행의 컬럼 값을 비교하여 더 큰값을 가져오도록 하였다.

 

동적계획법의 개념 자체는 이해하였는데 아직 로직을 짜는 부분은 좀 모자란 것같다.

어떻게 계획을 하고 기록을 할지 감이 잘 안오는데 그나마 어떻게 진행되어 나가는지 좀 적으면서 정리를 하여 이해를 돕도록 하여야 할것이다.