[Java] 백준 1535 안녕 - 실버2

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

1535번: 안녕

 

 

문제풀기 전 생각

• 물건을 쪼개서 넣을 수 있다면 그리디 문제이지만, 사람을 쪼갤 수 없으니 완전탐색이다
  • 최대 가치의 물건을 넣는 배낭문제로 생각할 수 있고
  • 완전탐색 백트래킹 방법으로 생각할 수 있다
• 배낭문제로 생각하면 배낭의 크기가 체력의 크기(100)이므로, 크지 않은 숫자라서 배낭문제로 풀기 적합하다
• 세준이의 체력은 최소 1까지만 줄어들 수 있고, 0이나 음수가 되면 안되는거 고려
• 백트래킹으로 생각해보면 체력이 0보다 작아지는 경우 dfs를 멈추는 식으로 구현

 

백트래킹 방법

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

//[baekjoon] java-1535
public class Main {

  private static int manCnt;
  private static int[] hp;
  private static int[] pleasure;
  private static int maxPleasure = 0;

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

    manCnt = Integer.parseInt(br.readLine());
    hp = new int[manCnt];
    pleasure = new int[manCnt];

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i =0; i<manCnt; i++)
      hp[i] = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    for (int i =0; i<manCnt; i++)
      pleasure[i] = Integer.parseInt(st.nextToken());

    dfs(100, 0, 0);

    System.out.println(maxPleasure);
  }

  static void dfs(int currHp, int currPleasure, int idx) {
    for (int i = idx; i<manCnt; i++) {

      //체력이 없으면 종료
      if (currHp - hp[i] <= 0) {
        if (currPleasure > maxPleasure)
          maxPleasure = currPleasure;

        continue;
      }

      //뺐을 때 체력이 있으면
      //마지막 인덱스 종료
      if (i == manCnt-1) {
        if (currPleasure + pleasure[i] > maxPleasure)
          maxPleasure = currPleasure + pleasure[i];
      } else {
        dfs(currHp-hp[i], currPleasure + pleasure[i], i+1);
      }
    }
  }
}

• 1234 234 34 4 이런식으로 비교하게 만들어서 visit 배열을 만들지 않았다
• 최대 체력 100, 기쁨 0으로 시작하여 dfs를 시작한다
• 체력이 없으면 최대기쁨을 갱신하고,
• 체력이 있으면
  • 마지막 인덱스일 때는 최대기쁨 갱신
  • 체력을 줄이고, 기쁨을 증가시켜 dfs를 다시 수행한다

 

배낭문제 풀이

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

//[baekjoon] java-1535
public class Main {

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

    int manCnt = Integer.parseInt(br.readLine());
    int[] hp = new int[manCnt+1];
    int[] pleasure = new int[manCnt+1];

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i =1; i<manCnt+1; i++)
      hp[i] = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    for (int i =1; i<manCnt+1; i++)
      pleasure[i] = Integer.parseInt(st.nextToken());

    int[][] arr = new int[manCnt+1][100];

    //체력 0
    for (int i =0; i<=manCnt; i++)
      arr[i][0] = 0;

    //사람 0명
    for (int i =0; i<100; i++)
      arr[0][i] = 0;

    for (int i =1; i<arr.length; i++) {
      for (int j=1; j<arr[0].length; j++) {
        if (hp[i] > j)
          arr[i][j] = arr[i-1][j];
        else //안담을경우 담을 경우
          arr[i][j] = Math.max(arr[i-1][j], arr[i-1][j-hp[i]] + pleasure[i]);
      }
    }

    System.out.println(arr[manCnt][99]);
  }
}

• 이차원 배열을 사용하여 배낭문제 풀듯이 풀었다

 

시간복잡도(배낭문제 VS 백트래킹)

• 위가 배낭문제, 아래가 백트래킹
• 배낭이 시간이 조금 더 덜걸린다