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

백준 16434 드래곤 앤 던전

풀이

방의 개수가 123,456개, 용사의 초기 공격력이 1이고 모든 방의 t == 1이며 몬스터의 체력과 공격력이 1,000,000이라는 최악의 경우를 생각해보았을 때, for문을 통해 최소 MaxHP를 찾으면 시간 초과가 발생할 수 있다고 생각하였습니다.

그래서 O(N)보다 빠른 O(logN)으로 최솟값을 찾을 수 있는 이분 탐색 을 이용하였습니다.

이 문제에서 주의할 점은 위의 최악의 경우를 생각해보면 알 수 있듯이 최소 MaxHP 값이 int의 범위를 벗어날 수도 있다는 것입니다.
저는 문제에서 고려할 최대 MaxHP인 end값을 영웅의 공격력이 영원히 1일 때, 몬스터를 잡기 위해 필요한 값인 a * h의 합으로 설정하였습니다. 하지만 다른 코드를 참고해보니 그냥 Long.MAX_VALUE - 1을 해도 되는 거 같습니다.

또 하나 주의해야 할 부분이 있습니다. 바로 영웅의 CurHP를 감소시킬 때입니다.
처음에 단순하게 영웅이 먼저 공격하기 때문에 (몬스터의 공격력 * (몬스터의 체력 / 현재 영웅의 공격력))을 CurHP에서 빼주면 된다고 생각하였습니다.
하지만 (몬스터의 체력 % 현재 영웅의 공격력) == 0이 되는 경우, 영웅이 몬스터에게 공격 받는 횟수는 (몬스터의 체력 / 현재 영웅의 공격력) - 1이 됩니다.
따라서 나머지가 0인 경우와 아닌 경우를 따로 처리해 주어야 합니다!

코드

import java.io.*;
public class B16434_DragonAndDungeon {
    static class Room {
        int t;
        int a;
        int h;

        public Room(int t, int a, int h) {
            this.t = t;
            this.a = a;
            this.h = h;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str[] = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int HAtk = Integer.parseInt(str[1]);
        long start = 1, end = 0;

        Room rooms[] = new Room[N];

        for(int i = 0;i < N;i++) {
            str = br.readLine().split(" ");
            int t = Integer.parseInt(str[0]);
            int a = Integer.parseInt(str[1]);
            int h = Integer.parseInt(str[2]);
            rooms[i] = new Room(t, a, h);
            if(t == 1) end += ((long)a * h);
        }

        while(start <= end) {
            long mid = (start + end) / 2;
            long HCurHp = mid;
            long tempHAtk = HAtk;
            boolean success = true;
            for(int i = 0;i < N;i++) {
                if(rooms[i].t == 1) {
                    if(rooms[i].h % tempHAtk == 0)
                        HCurHp -= rooms[i].a * ((rooms[i].h / tempHAtk) - 1);
                    else HCurHp -= rooms[i].a * (rooms[i].h / tempHAtk);
                    if(HCurHp <= 0) {
                        success = false;
                        break;
                    }
                }
                else if(rooms[i].t == 2) {
                    tempHAtk += rooms[i].a;
                    HCurHp += rooms[i].h;
                    if(HCurHp > mid) HCurHp = mid;
                }
            }

            if(success) end = mid - 1;
            else start = mid + 1;
        }

        System.out.println(start);
    }
}