[백준] 16434 드래곤 앤 던전 - Java

 

 

 

문제 출저

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

16434번: 드래곤 앤 던전

 

 

 

문제 풀이

용사의 공격력이 주어집니다. 그리고 방의 정보가 주어집니다. 방에는 포션이 있을 수가 있고 몬스터가 있을 수 있습니다. 포션이 있으면 용사의 공격력과 체력이 올라갑니다. 이 때, 체력은 최대 체력을 넘을 수 없습니다. 몬스터가 있을 경우 몬스터와 전투를 합니다. 용사가 먼저 공격하면서 서로 공격을 주고 받습니다. 둘 중 체력이 0 이하가 되면 전투가 끝납니다. 몬스터가 0 이하가 되면 용사는 탐색을 계속 합니다. 용사가 체력이 0 이하가 되면 다시 최대 체력을 설정해서 처음부터 도전합니다. 이 때, 방을 다 탐색하기 위해 용사의 최대 체력의 최솟값을 구해야 합니다. 

 

 

이분 탐색으로 문제를 풀었습니다.

용사의 최소 체력은 1입니다. 용사의 최대 체력은 용사의 공격력이 1이라고 가정 했을 때, 몬스터 공격력 * 몬스터 체력을 전부 더 한 값입니다. 이것이 최악의 경우에서 나올 수 있는 용사의 최대 체력입니다. 이분 탐색으로 최소 최대 체력을 찾습니다. 모든 방을 탐색할 수 있는지에 대한 여부를 true, false로 하여 탐색할 수 있으면 true, 탐색할 수 없다면 false를 반환합니다. true 면은 체력을 낮추고 다시 확인합니다. false면 체력을 높이고 다시 확인합니다.

 

모든 방을 탐색할 수 있는지에 대한 여부는 클래스를 이용했습니다. Room, Braver 클래스를 만들고 Braver에는 potion, battle 이라는 메소드를 만들어 포션을 먹을 때, 전투를 했을 때 로직을 처리했습니다. battle 로직을 만들 땐 while문을 이용했는데 이러면 여러 번 연산이 진행되어 비효율적입니다. while 반복이 아니라 계산을 통해 결과값을 유추하도록 로직을 다시 재구성했습니다. 

 

 

 

소스코드

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

/*
드래곤 앤 던전
https://www.acmicpc.net/problem/16434

이분 탐색
최댓값 설정 : 용사의 공격력을 1이라 생각하면 몬스터 공격 * 체력이 된다.

 */
public class Main {

  static int n;
  static int atk;
  static List<Room> rooms;
  static long hpMax;


  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    atk = Integer.parseInt(st.nextToken());

    rooms = new ArrayList<>();
    long max = 0;

    for(int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      int t = Integer.parseInt(st.nextToken());
      int a = Integer.parseInt(st.nextToken());
      int h = Integer.parseInt(st.nextToken());
      rooms.add(new Room(t, a, h));
      if(t == 1) max += ((long)a * h);
    }


    long min = 1;
    long answer = 0;

    while(min <= max) {
      hpMax = (max + min) / 2;

      if(check()) {
        max = hpMax - 1;
        answer = hpMax;
      }
      else {
        min = hpMax + 1;
      }
    }

    System.out.println(answer);

  }

  // 이 정도 체력이면 깰 수 있는지 여부
  public static boolean check() {
    Braver braver = new Braver(atk, hpMax);

    for(Room room : rooms) {
      if(room.t == 1) {
        if(!braver.battle(room.a, room.h)) return false;
      }
      if(room.t == 2) braver.potion(room.a, room.h);
    }

    return true;

  }


  // 방의 정보
  public static class Room {

    int t; // 1: 몬스터 2: 포션
    int a; // 공격력, 공격력 증가
    int h; // 생명력, 생명력 증가

    Room(int t, int a, int h) {
      this.t = t;
      this.a = a;
      this.h = h;
    }
  }

  public static class Braver {
    long atk; // 공격력
    long hp; // 체력

    Braver(long atk, long hp) {
      this.atk = atk;
      this.hp = hp;
    }

    // 포션을 마셨을 경우 공격력과 체력이 올라감
    // 체력은 최대 hp를 넘을 수 없다.
    void potion(int a, int h) {
      this.atk += a;
      this.hp = Math.min(hp+h, hpMax);
    }

    // 전투
    // while 쓸 경우 비효율적이다.
    boolean battle(int a, int h) {
      long braverAttack = h / atk;
      if(h % atk != 0) braverAttack += 1;
      long monsterAttack = hp / a;
      if(hp % a != 0) monsterAttack += 1;

      if(monsterAttack < braverAttack) {
        return false;
      }
      else {
        hp -= (a * (braverAttack - 1));
        return true;
      }
    }
  }

}