[Java] 백준 평범한 배낭

1. 문제 분석

 

배낭에 담을 수 있는 최고 가치의 물건을 넣는 문제다.

DP로 풀 수 있었고 DP테이블을 통해 문제를 해결했다.

	Weight 1	Weight 2	Weight 3	Weight 4	Weight 5	Weight 6	Weight 7
Item 1
Item 2
Item 3
Item 4

먼저 무게를 하나씩 증가시키면서 아이템을 넣을 수 있는지 없는지 확인한다.

못 넣는다면 전에 있는 값을, 넣는다면 큰 값을 넣어줘야 한다.

1. 무게가 1 ~ 2일 때

	Weight 1	Weight 2	Weight 3	Weight 4	Weight 5	Weight 6	Weight 7
Item 1	0	0
Item 2	0	0
Item 3	0	0
Item 4	0	0

현재 넣을 수 있는 무게가 1,2 이라면 테스트 케이스에 있는 무게를 전부 다 넣지 못한다. 그러므로 0을 넣어준다.

2. 무게가 3일 때

	Weight 1	Weight 2	Weight 3	Weight 4	Weight 5	Weight 6	Weight 7
Item 1	0	0	0
Item 2	0	0	0
Item 3	0	0	6
Item 4	0	0	6

무게가 3일 때는 (3, 6)을 넣어줄 수 있다. 그런데 Item 4일때는 왜 6일까?

우리는 지금 무게를 기준으로 최대 값을 구하고있다. 말 그대로 무게가 3일 때는 6일 최대이므로 넣어줄 수 없다면 전의 값을 넣어준다.

3. 무게가 4일 때

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

무게가 4일 때는 (4, 8)을 넣어줄 수 있다.

여기서 봐야할 점은 Item 3보다 Item 2를 넣을 때 더 높은 가치를 가지기 때문에 8을 넣어줬다.

여기서 우리는 앞의 DP 테이블(무게가 3일 때)의 값도 필요하다는 사실을 알았다.

4. 무게가 5 ~ 6일 때

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

무게가 5일 때는 (5, 12), 6일 때는 (6,13)을 넣어줄 수 있다.

6까지는 마찬가지로 높은 가치를 넣어주면 된다.

5. 무게가 7일 때

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

마지막으로 무게가 7일 때를 보자.

Item을 2까지 넣었을 때는 13이 가장 큰 가치를 가진다.

하지만 Item3까지 생각하면 (4,8), (3,6)을 통해 13보다 큰 14의 가치를 가진다.

 

이때 생각해보는 것이 남은 무게의 물건의 가치를 넣어주는 방법이다.

예를 들면 Item 3일때 (3,6)이므로 남은 무게가 4가 된다. 그러므로 7 - 3에서의 최대 무게를 구하면 된다.

Weight (7 -3), 즉 무게가 4이고 Item이 3일때의 무게를 추가해주면 된다.

정리

이제 나온 정보들을 기준으로 점화식을 세워보자.

dp[0][0] = 0으로 초기화하고 기본적으로 무게를 못 넣어준다면 0이 들어가므로

dp[nowWeight][nowItem] = dp[nowWeight - 1][nowItem]

 

만약 물건을 넣을 수 있다면 비교를 해줘야한다.

dp[nowWeight][nowItem] =

Max(전 무게에서의 최댓값, 현재 넣고자 하는 아이템의 가치 + 아이템을 넣고 남은 무게로 넣을 수 있는 아이템의 가치)

2. 구현

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int maxCount = Integer.parseInt(input[0]);
        int maxWeight = Integer.parseInt(input[1]);

        //무게, 가치
        int[][] item = new int[maxCount + 1][2];

        //데이터 넣어주기
        for (int i = 1; i <= maxCount; i++) {
            input = br.readLine().split(" ");
            item[i][0] = Integer.parseInt(input[0]);
            item[i][1] = Integer.parseInt(input[1]);
        }

        int[][] dp = new int[maxCount + 1][maxWeight + 1];

        //무게를 점차 늘려감
        for (int nowWeight = 1; nowWeight <= maxWeight; nowWeight++) {
            //해당 무게에 맞는 최대 가치 찾기
            for (int nowItem = 1; nowItem <= maxCount; nowItem++) {
                //기본적으로 앞에 있는 데이터 넣어주기
                dp[nowItem][nowWeight] = dp[nowItem - 1][nowWeight];

                //만약 넣고자 하는 아이템이 무게에 맞는다면?
                if (nowWeight - item[nowItem][0] >= 0) {
                    //넣고자 하는 가치 + (현재 넣을 수 있는 무게 - 넣고자 하는 아이템 무게)를 하고 남은 무게를 가진 아이템의 가치
                    dp[nowItem][nowWeight] = Math.max(dp[nowItem - 1][nowWeight], item[nowItem][1] + dp[nowItem - 1][nowWeight - item[nowItem][0]]);
                }
            }
        }
        System.out.println(dp[maxCount][maxWeight]);
    }
}

3. 마무리

이 문제는 구글링을 해도 이해가 안갔다. 그래서 코드를 복붙하고 하나씩 뜯어봤다.

실제로 내가 DP 테이블을 만들면서 진행하는게 이해가 잘갔고 나중에도 이렇게 문제를 풀어야겠다.