평범한 배낭 [JAVA] (백준 12865)

 

문제

문제 링크 : https://www.acmicpc.net/problem/12865

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	512MB	28422	10771	7140	36.222%

문제

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

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

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

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

출력

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

 

풀이

정말 모든 경우의 수를 고려해서 조합으로 풀게 된다면 문제의 시간복잡도는 다음과 같다.

$_{n}\mathrm{C}_{1} + _{n}\mathrm{C}_{2} + ... + _{n}\mathrm{C}_{n} = 2^n$

절대 불가능하기 때문에, 연산 수를 줄여야 한다.

처음에는 이전 무게에서의 최대 가치를 유지하면서 무게를 비교하려 했지만, 그렇게 하면 틀린다.

 

일단 우선적으로 생각한 방법은 다음과 같다.

1. 순서는 중요하지 않아야 한다. -> 1~3까지의 최대는 1,3일수 있으나, 1~4까지의 최대는 2,4일 수 있음.
2. 무게는 일정하지 않다. -> 어떻게 될 지 모르니 모든 무게에서의 경우를 다 고려해야 한다.

 

그렇게 결국 생각한 풀이는 다음과 같다.

우선 무게의 최대치가 100,000이므로, 각 index를 무게로 하는 배열을 만들고, 그 값을 가치로 한다.

이제 짐을 하나씩 추가해보도록 한다.

 

무게의 상한선 K부터 역순으로 탐색하면서,

만약 무게에 따른 가치가 있으면 (해당 무게 조합만큼이 가능하다면) -> 이 짐을 추가했을때 최대인지 고려하여 배열에 저장한다.

역순으로 탐색하는 이유는, 만약 무게 1부터 탐색하게 된다면, 짐을 계속 쌓아가면서 다음 무게로 중복이 되기 때문이다.

그리고 최종적으로, 해당 짐 1개만 담았을 때 역시 고려해주는 과정을 모든 짐에 대해 반복하면 문제를 해결할 수 있게 된다.

 

코드

import java.io.IOException;

public class Main {
   public static StringBuilder sb = new StringBuilder();
   public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
   public static void main(String[] args) throws IOException{

      String[] spl = br.readLine().split(" ");
      //물품 수
      int N = Integer.parseInt(spl[0]);

      //버틸수 있는 무게
      int K = Integer.parseInt(spl[1]);

      //각 물건 무게
      int[] W = new int[N];

      //가치
      int[] V = new int[N];

      //input
      for(int i=0; i<N; i++) {
         spl = br.readLine().split(" ");
         W[i] = Integer.parseInt(spl[0]);
         V[i] = Integer.parseInt(spl[1]);
      }

      int[] cache = new int[100001];

      for(int i=0; i<N;i++) {
          for(int j=K; j>=0; j--) {
              //가방 범위 내 일때, 이미 존재하는 무게 조합인가
              if(j + W[i] <= K && cache[j] != 0) {
                  //짐 추가 고려
                  if(cache[ j + W[i] ] < cache[j] + V[i]) {
                      cache[ j + W[i] ] = cache[j] + V[i];
                  }
              }
          }
          cache[W[i]] = Math.max(V[i], cache[W[i]]);
      }
      //answer
      int answer = 0;
      for(int i=0; i<=K; i++) {
         answer = Math.max(answer, cache[i]);
      }
      System.out.println(answer);
   }
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!