백준 16434 : 드래곤 앤 던전

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

16434번: 드래곤 앤 던전

[ 문제풀이 ]

최솟값을 찾는 최적화 문제이기 때문에 파라메트릭 서치를 활용하면 해결할 수 있다.

요새 파라메트릭 서치 문제를 자주 풀어서 그런지 최적 값을 구하는 문제를 보면 자연스럽게 dp, 그리디, 파라메트릭 서치 중 하나를 떠올리게 되는 것 같다.

주의해야할 점은 포션을 먹어도 Hmaxhp를 넘길 수 없는 조건과 용사가 몬스터를 먼저 공격한다는 점이다.

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

public class Main {
	
	static int N, HATK;
	static int[] t, a, h;
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			HATK = Integer.parseInt(st.nextToken());
			t = new int[N];
			a = new int[N];
			h = new int[N];
			for (int i = 0; i < N; ++i) {
				st = new StringTokenizer(br.readLine());
				t[i] = Integer.parseInt(st.nextToken());
				a[i] = Integer.parseInt(st.nextToken());
				h[i] = Integer.parseInt(st.nextToken());
			}
			
			long l = 0, r = 999999000001L * N;
			long ans = r;
			while (l <= r) {
				long m = (l + r) >> 1;
				if (isVaild(m)) {
					ans = m;
					r = m - 1;
				} else {
					l = m + 1;
				}
			}
			bw.write(ans + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static boolean isVaild(long Hmaxhp) {
		long Hcurhp = Hmaxhp, Hatk = HATK;
		for (int i = 0; i < N; ++i) {
			if (t[i] == 1) {
				long count = h[i] / Hatk;
				if (h[i] % Hatk == 0) count--;
				Hcurhp -= count * a[i];
				if (Hcurhp <= 0) return false;
			} else {
				Hatk += a[i];
				Hcurhp = Math.min(Hcurhp + h[i], Hmaxhp);
			}
		}
		return true;
	}
}