[백준] 16434번 - 드래곤 앤 던전 [Java][C++]

문제 링크

---

1. 문제 풀이

모든 몬스터를 쓰러트리기 위한 용사의 최대 생명력을 찾아야하는 문제로 매개 변수 탐색을 활용하면 간단하게 해결할 수 있다. 주어진 던전 정보를 통해 필요한 체력을 계산하는 것이 아니라 체력의 하한과 상한을 정하고 그 중간값으로 던전을 돌아보고 안되면 체력을 증가시키고 되면 체력을 감소시켜가며 던전을 돌 수 있는 최소 체력을 찾는 방식으로 해결했다.

공격력도 포션을 반복적으로 먹는 과정에서 오버플로우가 날 수 있음에 주의해야 하며 몬스터와의 전투를 반목문으로 구현할 경우 시간 초과가 발생한다. 따라서 미리 몬스터와 용사가 각각 몇 번의 공격으로 서로를 물리칠 수 있는지 계산해서 몬스터의 공격 횟수가 더 많을 경우 용사가 이기는 전투로 판단했다. 이때 몬스터의 공격 횟수는 용사의 공격 횟수 $-1$ 이다.

---

2. 코드

1. 이분 탐색 + 매개 변수 탐색 [Java]

Hero 정적 내부 클래스를 활용해서 초기 설정 및 포션을 먹는 로직을 두었다.

import java.io.*;
import java.util.*;

public class Main {

    static class Hero {
        long hMax;
        long hCur;
        long hAtk;  // 포션을 먹는 과정에서 공격력도 오버플로우 주의

        public Hero(long hMax, int hAtk) {
            this.hMax = hMax;
            this.hCur = hMax;
            this.hAtk = hAtk;
        }

        void drink(int atk, int hp) {
            hAtk += atk;
            hCur = Math.min(hCur + hp, hMax);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int hAtk = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][3];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
            map[i][2] = Integer.parseInt(st.nextToken());
        }

        System.out.println(lowerBound(map, hAtk));
    }

    static long lowerBound(int[][] map, int hAtk) {
        long left = 1;
        long right = Long.MAX_VALUE - 1;

        while (left < right) {
            long mid = left + (right - left) / 2;

            boolean result = simul(map, new Hero(mid, hAtk));
            if (!result) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    static boolean simul(int[][] map, Hero hero) {
        for (int[] stage : map) {
            int t = stage[0];
            int a = stage[1];
            int h = stage[2];

            if (t == 1) {
                long heroAtkCnt = (h + hero.hAtk - 1) / hero.hAtk;
                long monsAtkCnt = (hero.hCur + a - 1) / a;

                if (heroAtkCnt <= monsAtkCnt) {
                    hero.hCur -= a * (heroAtkCnt - 1);
                } else {
                    return false;
                }
            } else {
                hero.drink(a, h);
            }
        }

        return true;
    }
}

2. 이분 탐색 + 매개 변수 탐색 [C++]

던전 정보를 전역 벡터로 관리하는 방식으로 구현했다.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> mp;

bool simul(long long hMax, long long hAtk) {
    long long hCur = hMax;

    for (auto row : mp) {
        int t = row[0];
        int a = row[1];
        int h = row[2];

        if (t == 1) {
            long long heroAtkCnt = (h + hAtk - 1) / hAtk;
            long long monsAtkCnt = (hCur + a - 1) / a;

            if (heroAtkCnt <= monsAtkCnt) {
                hCur -= a * (heroAtkCnt - 1);
            } else {
                return false;
            }
        } else {
            hAtk += a;
            hCur = min(hCur + h, hMax);
        }
    }

    return true;
}

long long lower_bound_param(int hAtk) {
    long long left = 1;
    long long right = LLONG_MAX - 1;

    while (left < right) {
        long long mid = left + (right - left) / 2;

        bool res = simul(mid, hAtk);
        if (!res) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, hAtk;
    cin >> n >> hAtk;

    mp.assign(n, vector<int>(3));
    for (auto& row : mp) cin >> row[0] >> row[1] >> row[2];

    cout << lower_bound_param(hAtk);
}

---

3. 풀이 정보

1. 이분 탐색 + 매개 변수 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	564 ms	54184 KB	2211 B

2. 이분 탐색 + 매개 변수 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	388 ms	8880 KB	1241 B

---