아이디어

• 구하고자 하는 답인 $H_{MaxHp}$에 대해 매개변수 이진탐색 한다.
  • 초기 left = 1, right = 123000 * 100만 * 100만 + 1이다.
    • 최악의 경우 공격력이 100만인 적을 공격력 1로 싸울 때 100만 대를 버텨야하므로
  • 설정한 최대체력으로 게임을 시뮬레이션하여 클리어하는지 확인한다.
    • 이때, 몬스터와의 전투를 그대로 구현하면 시간초과를 받는다.
    • 용사와 몬스터의 필요 공격 수를 비교해 승패를 결정하고 용사의 남은 체력을 계산한다.
  • 게임을 클리어하는 최소 최대체력을 찾는다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N;
	static long ATK, atk, curHp;
	static Room[] rooms;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		ATK = Integer.parseInt(tk.nextToken());
		
		rooms = new Room[N+1];
		for (int i=1; i<=N; i++) {
			tk = new StringTokenizer(rd.readLine());
			int t = Integer.parseInt(tk.nextToken());
			int a = Integer.parseInt(tk.nextToken());
			int h = Integer.parseInt(tk.nextToken());
			rooms[i] = new Room(t, a, h);
		}
		
		long l = 1L;
		long r = 123_456L * 1_000_000L * 1_000_000L + 1L;
		long m = -1L;
		while (l < r) {
			m = (l + r) / 2;
			if (simulate(m))
				r = m;
			else
				l = m + 1;
		}

		System.out.println(l);
	}
	
	static boolean simulate(long maxHp) {
		atk = ATK;
		curHp = maxHp;
		for (int i=1; i<=N; i++) {
			Room room = rooms[i];
			switch (room.t) {
			case 1:
				long enemyAtk = room.a;
				long enemyHp = room.h;
				
				long hit = (enemyHp + atk - 1) / atk;
				long enemyHit = (curHp + enemyAtk - 1) / enemyAtk;
				if (hit <= enemyHit)
					curHp -= (hit - 1) * enemyAtk;
				else
					return false;
				break;
			default:
				atk += room.a;
				curHp = Math.min(curHp + room.h, maxHp);
				break;	
			}
		}
		return true;
	}
	
	static class Room {
		int t, a, h;
		Room(int t, int a, int h) {
			this.t = t;
			this.a = a;
			this.h = h;
		}
	}
}

메모리 및 시간

• 메모리: 53204 KB
• 시간: 892 ms

리뷰

• 재밌는 난이도의 구현문제 2
• (23. 11. 15.) 이전까지 잘못된 코드를 게시하고 있었다. 수정 완료.