[백준]#16434 드래곤 앤 던전

문제

용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다.

용사에게는 세 종류의 능력치가 있습니다.

• $H_{MaxHP}$ : 용사의 최대 생명력입니다. 이 값은 1이상이어야 하며 던전에 들어간 이후로 변하지 않습니다.
• $H_{CurHP}$ : 현재 용사의 생명력입니다. 던전에 들어가기 전 이 값은 용사의 최대 생명력 $H_{MaxHP}$와 같습니다. 이 값은 $H_{MaxHP}$보다 커질 수 없습니다.
• $H_{ATK}$ : 용사의 공격력입니다.

던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동 할 수 있습니다. 방에는 포션이 있거나 몬스터가 있는데 몬스터가 있을 경우 몬스터를 쓰러트려야지 다음방으로 이동 할 수 있습니다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있습니다.

몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.

1. 용사의 공격력 $H_{ATK}$만큼 몬스터의 생명력을 깎습니다.
2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
3. 몬스터의 공격력만큼 용사의 생명력 $H_{CurHP}$를 깎습니다.
4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
5. 다시1부터 진행합니다.

포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 $H_{CurHP}$가 일정량 회복되고 공격력 $H_{ATK}$도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 $H_{MaxHP}$보다 큰 경우 용사의 현재 생명력 $H_{CurHP}$가 최대 생명력 $H_{MaxHP}$와 같아집니다.

용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 $H_{MaxHP}$를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.

용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 $H_{MaxHP}$를 여러분이 계산해주면 좋겠다고 합니다.

입력

첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 $H_{ATK} (1 ≤ H_{ATK} ≤ 1,000,000)$ 가 주어집니다.

i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 $t_i, a_i, h_i (t_i ∈ {1, 2}, 1 ≤ a_i, h_i ≤ 1,000,000)$ 가 주어집니다.

$t_i$가 1인 경우 공격력이 $a_i$이고 생명력이 $h_i$인 몬스터가 있음을 나타내고, $t_i$가 2인 경우 용사의 공격력 $H_{ATK}$를 $a_i$만큼 증가시켜주고 용사의 현재 생명력 $H_{CurHP}$를 $h_i$만큼 회복시켜주는 포션이 있음을 나타냅니다.

출력

용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 $H_{MaxHP}$를 출력합니다.

예제 입력 1

3 3
1 1 20
2 3 10
1 3 100

예제 출력 1

49

예제 입력 2

1 1
1 1000000 1000000

예제 출력 2

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;
        }
    }
}