[백준 알고리즘] 12865번 자바(Java) 평범한 배낭

조건

문제

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

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

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

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

출력

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

 

풀이

이 문제는 물품과 가치가 들어올때마다 0~K(버틸수있는 무게)무게에 따른 가치합의 최댓값을 계속 초기화시켜줘야한다. 아래 예시처럼 물품의 수가 4개이고 준서가 버틸수있는무게가 7이면우리는 물품이 들어올때마다 무게 1인경우, 2인 경우, ... 7인경우 매번 초기화를 시켜줘야한다.그럼 초기화시키는 기준은 어떻게 될지가 고민포인트인데 예시를 들어보겠다.무게 6과 4인 물품이 들어오고 3의 물품이 들어올때 무게 4,5,6,7을 기존 무게와 들어온 물품의 무게를 뺀 인덱스에 물품의 가치를 더한값을 비교하면 된다.무게 4일때의 가치합의 최댓값은 

1. 기존 무게 4일때 최댓값 또는

2. 무게1일때 최댓값+3무게의 물품 가치

이렇게 2가지를 비교해주면서 초기화해주면된다. 따라서 시간복잡도는 N*K가 된다.(물건이 들어올때마다 매번 모든 무게를 초기화해주기때문이다.)아래 표의 예시를 들어 설명을 들겠다.

 

가치값 13인 무게 6 물건 들어왔을때

가치값 8인 무게 4 물건 들어왔을때

가치값 6인 무게 3 물건 들어왔을때

 

가치값  12인 무게 5 물건 들어왔을때

이렇게 해서 무게 7일때는 14가 답이 된다. 그리고 추가로 한물건이 여러번 중복되는것을방지하고자 2단 배열로 만들어서 값을 옮기는 식으로 했다.

 

 

예제 입력 예시

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;

//12865번

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] dp = new int[K+1][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            if(W <=K){
                //새로 배정받은값 dp[][1]에 저장, 바로배정받은값 dp[]에 저장하면 높은 index일때
                //전에 사용한 물건 재사용문제가 생김
                for (int j = 0; j <= K-W; j++) {
                    dp[j+W][1] = Math.max(dp[j+W][0],dp[j][0]+V);
                }
                //새로 배정받은 물건적용된 값으로 변경
                for (int j = 1; j <=K; j++) {
                    dp[j][0] = dp[j][1];
                }
            }
        }

        System.out.println(dp[K][0]);
    }
}

 

 

 

 

문제 출처

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

12865번: 평범한 배낭