[BOJ/백준] 12865번 - 평범한 배낭(Java 풀이/해답)

문제 바로가기: https://www.acmicpc.net/problem/12865

 

백준 Class 4 평범한 배낭(standard) 문제이다

난이도는 골드 5로 DP를 이해하거나, 냅색 알고리즘에 대한 내용을 알고 있으면 수월하게 풀 수 있다

---

문제

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

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

준서가 여행에 필요하다고 생각하는 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

 

조건

시간제한: 2초

메모리 제한: 512MB

---

접근

https://www.youtube.com/watch?v=rhda6lR5kyQ

 

영상을 통해 냅색에 대해 먼저 알고 가는 것이 수월하다

배열을 생성하고 무게에 따른 최댓값을 갱신하면서 진행한다

N-Qeen과 유사하게 1차원 배열로도 줄일 수 있지 않을까 싶었다

 

행은 아이템의 수만큼, 열은 무게의 크기만큼 진행한다

그리고 배열을 돌면서 현재 아이템의 무게가 포함 가능할 때, 불가능할 때로 분기하여 진행한다

 

풀이

1. 물품의 수 N, K를 입력받는다

2. 물품 수를 저장하기 위한 Node를 생성하고, 해당 Node를 저장할 배열을 생성하여 입력한다

3. 저장 완료된 배열을 활용하여 값을 저장할 DP 배열을 생성한다

4. DP 배열을 반복문으로 탐색한다

5. 현재 행에 일치하는 Node를 가져온다

6. 열(무게값)을 돌면서, 열 - 현재 아이템의 무게에 따라 분기한다

   6-1. 해당 값이 0보다 크다면(현재 아이템을 넣을 수 있다면), 바로 위의 열(이전 아이템까지만 포함할 때의 최댓값) 값과 r-1(이전 아이템 포함)행의 c-지금 아이템 무게(열 - 현재 아이템 무게) + 현재 아이템 가치(현재 무게(c)를 넘지 않는 상황) 중 큰 값을 DP에 넣어준다

   6-2. 만일 지금 아이템을 넣을 때 열 값을 초과한다면(무게가 오버된다면) 바로 위의 값(지금까지의 최댓값)을 넣는다

7. 마지막 DP의 값(dp[N][K])을 출력한다 - K 무게를 넘지 않으면서 가치가 최대가 되는 값

 

 

코드

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

public class Main {

    static class Node {
        int weight, value;

        public Node(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }


    public static void main(String[] args) throws IOException {
        // 1. 기본 입출력 사용 가져오기

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 어차피 하나만 출력하면 되니까, 스트링 빌더는 사용하지 않는다

        // 2. 물품의 수 N, 버틸 수 있는 무게의 수 K 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        /* N개 줄에 걸쳐 각 물건의 무게 W, 가치 V가 주어진다
         * 이 값을 저장하기 위한 테이블을 생성하자
         * N의 최대 크기는 100이므로 메모리 차지가 크진 않다
         * 0번 인덱스부터 사용하면 되겠다
         * 0번 인덱스에 2개의 칼럼을 넣어 2차원 배열로 만들지, Node와 같은 클래스를 만들지
         * 아마 가시적으로 보기에는 클래스를 만드는 것이 좋아보인다. 메서드 변수명으로
         * 확실히 볼 수 있으니까
        */

        // 3. 배낭의 정보를 저장할 클래스와 배열 생성하기
        Node[] items = new Node[N];

        // 4. 배낭 정보 저장
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            items[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // 5. 값을 저장할 dp배열 생성
        // 행: 아이템의 개수
        // 열: 무게 값
        // 배열 값: 최대 가치
        int[][] dp = new int[N+1][K+1];

        // 6. dp 배열의 값을 넣어주기
        // 최대 100 * 100_000 이므로, 2억(2초)을 넘지 않음
        for(int r = 1; r <= N; r++) {
            Node cur = items[r - 1]; // 현재 노드 값

            for(int c = 1; c <= K; c++) {
                // 7. 현재 무게 인덱스 값이랑 현재 아이템 무게를 더한게 최대 무게를 넘어선 안됨
                if(c - cur.weight >= 0) {
                    dp[r][c] = Math.max(dp[r-1][c], dp[r - 1][c-cur.weight] + cur.value);
                } else {
                    dp[r][c] = dp[r-1][c];
                }
            }
        }

        // 정답은 마지막까지 돌았을 때 최대 무게
        System.out.println(dp[N][K]);

    }
}

 

 

꼭 영상을 보고 해당 로직을 이해한 뒤 풀어보길 바랍니다!