용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다.
용사에게는 세 종류의 능력치가 있습니다.
던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동 할 수 있습니다. 방에는 포션이 있거나 몬스터가 있는데 몬스터가 있을 경우 몬스터를 쓰러트려야지 다음방으로 이동 할 수 있습니다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있습니다.
몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.
포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 가 일정량 회복되고 공격력 도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 보다 큰 경우 용사의 현재 생명력 가 최대 생명력 와 같아집니다.
용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.
용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 를 여러분이 계산해주면 좋겠다고 합니다.
첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 가 주어집니다.
i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 가 주어집니다.
가 1인 경우 공격력이 이고 생명력이 인 몬스터가 있음을 나타내고, 가 2인 경우 용사의 공격력 를 만큼 증가시켜주고 용사의 현재 생명력 를 만큼 회복시켜주는 포션이 있음을 나타냅니다.
용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 를 출력합니다.
3 3
1 1 20
2 3 10
1 3 100
49
1 1
1 1000000 1000000
999999000001
이 문제는 이분탐색 알고리즘을 이용해서 풀 수 있었다. 이분 탐색을 많이 사용해보진 않아서 금방 알고리즘을 설계하진 못했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N;
static Pair[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
int ATK = Integer.parseInt(input[1]);
arr = new Pair[N];
long left = 1;
long right = (long)Math.pow(10, 12);
long ans = 0;
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
arr[i] = new Pair(Integer.parseInt(input[0]), Integer.parseInt(input[1]), Integer.parseInt(input[2]));
}
while(left<=right) {
long H = (left+right)/2;
if(check(ATK, H)) {
right = H-1;
ans = H;
}
else
left = H+1;
}
System.out.println(ans);
}
public static boolean check(long atk, long h) {
long H = h;
long ATK = atk;
for(int i=0; i<N; i++) {
if(arr[i].t==1) {
long cnt = arr[i].h/ATK;
if(arr[i].h%ATK==0) cnt--;
H -= cnt*arr[i].a;
if(H<=0)
return false;
}
else {
ATK += arr[i].a;
H = Math.min(h, H+arr[i].h);
}
}
return true;
}
public static class Pair {
int t;
int a;
int h;
public Pair(int t, int a, int h) {
this.t = t;
this.a = a;
this.h = h;
}
}
}