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

이분탐색 문제입니다.

최대체력을 기준으로 이분탐색을 진행합니다.
해당체력으로 용을 잡을 수 있다면
=> right = mid - 1;
해당체력으로 용을 잡을 수 없다면
=> left = mid + 1;

이 문제는 간단한 이분탐색이지만 Integer값을 넘어가게 되면서
해당 문제를 고치느라 시간을 썼습니다.

Long타입으로 선언해주고 1_000_000 * 1_000_000의 결과값인 999999000001를 사용해서 아래와 같이 썼습니다.

Long right = 999999000001L * n;

 

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

public class Main {

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

    int n = Integer.parseInt(st.nextToken());
    Long a = Long.parseLong(st.nextToken());

    int[][] map = new int[n][3];
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      map[i][0] = Integer.parseInt(st.nextToken());
      map[i][1] = Integer.parseInt(st.nextToken());
      map[i][2] = Integer.parseInt(st.nextToken());
    }

    Long left = 1L;
    Long right = 999999000001L * n;
    
    while (left <= right) {
      Long attack = a;
      Long maxHp = (left + right) / 2;
      Long hp = maxHp;
      boolean isKill = true;

      for (int i = 0; i < n; ++i) {
        if (map[i][0] == 1) {
          hp -= map[i][1] * ((map[i][2] - 1) / attack);
          if (hp <= 0) {
            isKill = false;
            break;
          }
        } else if (map[i][0] == 2) {
          attack += map[i][1];
          hp = Math.min(hp + map[i][2], maxHp);
        }
      }

      if (isKill) {
        right = maxHp - 1L;
      } else {
        left = maxHp + 1L;
      }
    }

    bw.write(left + "");
    bw.close();
  }
}