이번에는 백준 16434번 드래곤 앤 던전 문제를 풀어보았습니다.
용사가 던전을 끝까지 통과할 수 있는 최소 최대 체력 HMaxHP를 구해야 합니다.
특정 HMaxHP로 던전을 클리어할 수 있는지 판별할 수 있고, 최대 체력이 커질수록 클리어 가능성이 높아지므로 이분탐색 + 시뮬레이션으로 해결하였습니다.
문제 설명
용사는 초기 공격력 HATK를 가지고 던전에 들어갑니다.
던전의 각 방은 다음 두 종류 중 하나입니다.
- 몬스터 방
- 포션 방
몬스터 방에서는 용사가 먼저 공격하고, 몬스터가 살아 있다면 반격을 받습니다.
포션 방에서는 공격력이 증가하고 현재 체력이 회복됩니다.
단, 현재 체력은 최대 체력 HMaxHP를 넘을 수 없습니다.
이때 용사가 마지막 방까지 살아남을 수 있는 최소 HMaxHP를 구하는 문제입니다.
풀이 아이디어
최대 체력 HMaxHP를 어떤 값으로 정했을 때 던전을 클리어할 수 있는지 확인하는 함수를 만듭니다.
현재 최대 체력으로 던전을 통과할 수 있다면 더 작은 최대 체력에서도 가능한지 확인합니다.
반대로 클리어하지 못한다면 더 큰 최대 체력이 필요합니다.
따라서 가능한 범위가 다음과 같은 형태가 됩니다.
불가능 불가능 불가능 가능 가능 가능 ...이 특성을 이용하여 이분탐색으로 최소 가능한 최대 체력을 찾습니다.
각 몬스터 방에서는 실제로 한 턴씩 전투하지 않고, 몬스터가 용사를 몇 번 공격하는지를 계산하여 한 번에 체력을 차감하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
long long int HmaxHP,HcurHP,HATK,N;
struct room_struct{
int type,atk,hp;
};
vector<room_struct> rooms;
bool check_valid() {
long long int temp_atk = HATK;
for (room_struct room : rooms) {
if (room.type == 1) {
if(room.hp <= temp_atk) continue;
else {
long long hitCount = (room.hp - 1) / temp_atk;
long long need = hitCount * room.atk;
if (HcurHP <= need) return false;
else {
HcurHP -= need;
}
}
} else {
temp_atk += room.atk;
HcurHP = min(HmaxHP, HcurHP + room.hp);
}
}
return true;
}
long long int ret = LLONG_MAX;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> HATK;
for (int i=0; i<N; i++) {
int t,a,h;
cin >> t >> a >> h;
rooms.push_back({t,a,h});
}
long long int high = 1e18, low = 1;
while(low <= high) {
HmaxHP = (high + low) / 2;
HcurHP = HmaxHP;
if (check_valid()) {
ret = min(ret, HmaxHP);
high = HmaxHP-1;
} else {
low = HmaxHP+1;
}
}
cout << ret << '\n';
return 0;
}풀이 흐름
-
방의 개수와 초기 공격력을 입력받습니다.
-
각 방의 정보를 구조체 벡터에 저장합니다.
-
최대 체력의 탐색 범위를
1 ~ 1e18로 설정합니다. -
중간값을 현재 최대 체력
HMaxHP로 설정합니다. -
현재 체력
HCurHP를 최대 체력과 같은 값으로 초기화합니다. -
check_valid()를 이용하여 해당 최대 체력으로 던전을 통과할 수 있는지 확인합니다. -
가능하다면 더 작은 최대 체력을 찾기 위해 왼쪽 구간을 탐색합니다.
-
불가능하다면 더 큰 최대 체력을 찾기 위해 오른쪽 구간을 탐색합니다.
-
최소 가능한 최대 체력을 출력합니다.
구현 포인트
1. 방 정보 저장
struct room_struct{
int type,atk,hp;
};각 방마다 다음 정보를 저장하였습니다.
type : 방의 종류
atk : 몬스터 공격력 또는 증가 공격력
hp : 몬스터 체력 또는 회복량각 방의 정보를 벡터에 저장해두고, check_valid()를 수행할 때 순서대로 확인합니다.
2. 최대 체력을 기준으로 이분탐색
long long int high = 1e18, low = 1;최대 체력은 최소 1 이상이어야 하므로 low = 1로 설정하였습니다.
상한은 충분히 큰 값인 1e18로 설정하였습니다.
이후
HmaxHP = (high + low) / 2;를 통해 현재 확인할 최대 체력을 정합니다.
3. 매 이분탐색마다 현재 체력 초기화
HcurHP = HmaxHP;던전에 처음 입장할 때 현재 체력은 최대 체력과 같습니다.
따라서 새로운 HMaxHP 후보를 확인할 때마다 현재 체력을 다시 초기화해야 합니다.
4. 공격력은 별도 변수로 관리
long long int temp_atk = HATK;포션 방을 지나면 공격력이 계속 증가합니다.
하지만 이분탐색의 다음 후보를 검사할 때는 다시 원래 초기 공격력에서 시작해야 합니다.
따라서 전역 HATK를 직접 변경하지 않고 temp_atk에 복사하여 사용합니다.
5. 몬스터를 한 번에 잡는 경우
if(room.hp <= temp_atk) continue;몬스터의 체력이 현재 용사의 공격력보다 작거나 같다면 첫 공격에 바로 죽습니다.
용사가 먼저 공격하므로 몬스터는 반격하지 못합니다.
따라서 체력 감소 없이 다음 방으로 넘어갑니다.
6. 몬스터의 반격 횟수 계산
몬스터의 체력이 더 크다면 몬스터가 몇 번 반격하는지를 계산해야 합니다.
long long hitCount = (room.hp - 1) / temp_atk;몬스터를 죽이는 데 필요한 용사의 공격 횟수가
ceil(room.hp / temp_atk)라면, 마지막 공격에서는 몬스터가 죽기 때문에 반격하지 못합니다.
따라서 몬스터의 반격 횟수는
ceil(room.hp / temp_atk) - 1입니다.
이를 정수 연산으로 표현하면
(room.hp - 1) / temp_atk이 됩니다.
7. 몬스터에게 받는 총 피해
long long need = hitCount * room.atk;몬스터가 hitCount번 반격하고 한 번 공격할 때마다 room.atk만큼 피해를 받으므로 총 피해량은 두 값을 곱하면 됩니다.
이렇게 하면 전투를 실제 턴 단위로 반복하지 않고 바로 결과를 계산할 수 있습니다.
8. 죽는지 확인
if (HcurHP <= need) return false;용사가 받게 될 피해가 현재 체력 이상이라면 전투 도중 체력이 0 이하가 됩니다.
따라서 해당 최대 체력으로는 던전을 클리어할 수 없습니다.
반대로 살아남을 수 있다면
HcurHP -= need;를 통해 현재 체력만 감소시킵니다.
9. 포션 방 처리
temp_atk += room.atk;포션을 먹으면 공격력이 증가합니다.
이 공격력은 이후 모든 몬스터 방에 계속 적용됩니다.
현재 체력도 회복됩니다.
HcurHP = min(HmaxHP, HcurHP + room.hp);단, 현재 체력은 최대 체력을 넘어갈 수 없기 때문에 min()을 사용하였습니다.
10. 현재 최대 체력으로 클리어 가능한 경우
if (check_valid()) {
ret = min(ret, HmaxHP);
high = HmaxHP-1;
}현재 HMaxHP로 던전을 통과할 수 있다면 정답 후보입니다.
하지만 더 작은 최대 체력으로도 통과할 수 있을 수 있으므로 탐색 범위를 왼쪽으로 줄입니다.
11. 클리어할 수 없는 경우
else {
low = HmaxHP+1;
}현재 최대 체력으로는 중간에 죽는다는 뜻입니다.
따라서 이보다 작은 최대 체력 역시 클리어할 수 없으므로 더 큰 값만 확인하면 됩니다.
12. 이분탐색이 가능한 이유
최대 체력이 K일 때 던전을 클리어할 수 있다고 가정합니다.
그러면 K보다 더 큰 최대 체력을 가지고 시작하면 처음 체력도 더 많고, 포션을 통해 회복할 수 있는 최대치도 더 커집니다.
따라서 K보다 큰 값에서도 항상 클리어할 수 있습니다.
즉, 최대 체력에 대한 가능 여부가 다음과 같이 단조성을 가집니다.
false false false true true true ...따라서 처음으로 true가 되는 최대 체력을 이분탐색으로 찾을 수 있습니다.
13. long long을 사용하는 이유
방의 개수는 최대 123,456개이고, 몬스터의 공격력과 체력도 최대 1,000,000입니다.
여러 전투에서 필요한 체력을 계산하면 int 범위를 넘어갈 수 있습니다.
따라서 다음 값들을 long long으로 관리하였습니다.
long long int HmaxHP,HcurHP,HATK,N;총 피해량 역시
long long hitCount
long long need로 계산하였습니다.
시간복잡도
check_valid()에서는 모든 방을 한 번씩 확인하므로
O(N)의 시간이 필요합니다.
최대 체력 범위에 대해 이분탐색을 수행하므로 대략
O(log 10^18)번 검사합니다.
따라서 전체 시간복잡도는
O(N log 10^18)입니다.
log₂(10^18)은 약 60이므로 N이 최대 123,456이어도 충분히 해결할 수 있습니다.
