백준 12865(평범한 배낭)

안녕하세요!

오늘도 알고리즘 문제를 풀어볼까해요.

오늘 풀 문제는 평범한 배낭이라는 DP문제에요.

난이도는 골드5입니다.

문제

코드

시간초과 코드

  
package com.company;

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

class Pair{
  private int weight;
  private int value;

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

  public int getWeight(){
      return this.weight;
  }

  public int getValue(){
      return this.value;
  }
}

public class Main {
  private static int maxValue;
  private static int objCnt;
  private static int result = 0;
  private static List<Pair> list = new ArrayList<Pair>();

  private static void getMaxValue(int idx, int weight, int value){
      if(idx >= objCnt)
          return ;
      //idx over 방지

      Pair obj = list.get(idx);
      int havingWeight = obj.getWeight() + weight;
      int havingValue = obj.getValue() + value;
      if(obj.getWeight() > maxValue || havingWeight > maxValue)
          return ;

      for(int i = idx+1; i <= objCnt; i++) {
          getMaxValue(i, havingWeight, havingValue);
      }
      result = Math.max(result, havingValue);
  }

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());

      //init
      objCnt = Integer.parseInt(st.nextToken());
      maxValue = Integer.parseInt(st.nextToken());
      for(int i = 0; i < objCnt; i++){
          StringTokenizer tmp = new StringTokenizer(br.readLine());
          int weight = Integer.parseInt(tmp.nextToken());
          int value = Integer.parseInt(tmp.nextToken());
          list.add(new Pair(weight, value));
      }

      list.sort(new Comparator<Pair>() {
          @Override
          public int compare(Pair o1, Pair o2) {
              if(o1.getWeight() == o2.getWeight())
                  return o2.getValue() - o1.getValue();
              return o1.getWeight() - o2.getWeight();
          }
      });

      getMaxValue(0, 0, 0);

      System.out.println(result);
  }
}

성공 코드

package com.company;

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

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());

      //init
      int objCnt = Integer.parseInt(st.nextToken());
      int maxValue = Integer.parseInt(st.nextToken());

      int dp [][] = new int [objCnt + 1][maxValue+1];
      for(int i = 1; i < objCnt + 1; i++){
          StringTokenizer tmp = new StringTokenizer(br.readLine());
          int weight = Integer.parseInt(tmp.nextToken());
          int value = Integer.parseInt(tmp.nextToken());

          for(int j = 1; j < maxValue + 1; j++){
              dp[i][j] = dp[i-1][j];
              if(j - weight >= 0){
                  dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight] + value);
              }
          }
      }

      System.out.println(dp[objCnt][maxValue]);
  }
}  

• 접기/펼치기는 왜 미리보기에서만 될까요...?