드래곤 앤 던전
1.설계(10)
-
문제 해석
- 용사가 N번째 방에 있는 공주를 구출하는 문제입니다.
- HMaxHp: 용사의 최대 생명력, HCurHp: 현재 생명력, HATK : 공격력
- i번째 방을 통해서만 i+1방으로 이동이 가능합니다.
-
몬스터 방일 경우 다음 과정을 반복합니다.
a. 용사의 공격력만큼 몬스터의 생명력을 깎습니다.
b. 몬스터 생명력이 0 이하이면 다음방으로 이동합니다.
c. 몬스터의 공격력만큼 생명력이 깎입니다.
d. 용사의 생명력이 0 이하이면 사망합니다.
- 포션방일 경우 ACur, HCurHp가 증가합니다.
- 공주를 구출하기 위한 최소의 HMaxHp를 구합니다.
-
설계
- HMaxHp가 될 수 있는 최대값은 (10^6)^3=> 10^18 이 됩니다(A * H * N). 그러므로 전반적으로 long long 자료형을 사용합니다.
- HMaxHp를 이분탐색으로 지정한 다음, 해당 HMaxHp로 공주 구출 가능 여부를 검토합니다. => O(log(10^18))
- N개의 방에 대해 몬스터 방일 경우에는, Hi/Acur <= Hcur/Ai 를 만족할 경우 계속 진행합니다. => O(N)
- 시간복잡도는 대략 O(N*log(10^18))로 정해진 시간안에 풀이가 가능합니다.
2.구현(25)
- 코드
#include <iostream>
#define MAXN 1000000
typedef long long ll;
#define INF ll(1e18)
using namespace std;
int N;
ll Ainit;
struct node {
int mode;
ll A;
ll H;
};
node arr[MAXN];
ll ans = INF;
bool possible(ll HMax) {
ll Acur = Ainit;
ll Hcur = HMax;
for (int i = 0; i < N; i++) {
if (arr[i].mode == 1) {
ll monster = arr[i].H / Acur;
if (arr[i].H % Acur != 0) monster++;
ll human = Hcur / arr[i].A;
if (Hcur % arr[i].A != 0) human++;
if (monster <= human) {
Hcur = Hcur - (monster - 1) * arr[i].A;
}
else {
return false;
}
}
else {
Acur += arr[i].A;
Hcur += arr[i].H;
if (Hcur > HMax) Hcur = HMax;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> Ainit;
for (int i = 0; i < N; i++) {
int mode;
ll A, H;
cin >> mode >> A >> H;
arr[i] = { mode,A,H };
}
ll high = INF;
ll low = 0;
while (low <= high) {
ll mid = (low + high) / 2;
if (possible(mid)) {
high = mid - 1;
ans = mid;
}
else {
low = mid + 1;
}
}
cout << ans << "\n";
return 0;
}
-
디버깅
- Hi/Acur와 Hcur/Ai를 계산할 때, 해당 숫자보다 많이 반복을 해야하므로 올림을 해줘야 합니다. 처음에 이처럼 구현을 하지 않아 시간이 조금 더 걸렸습니다.
-
제출결과
176ms
3.마무리
- 다른 분의 코드를 보니 저와 같이 이분탐색으로 구현하지 않고 수학적 접근을 통해 풀이를 하였습니다. 이 접근방법으로 풀이를 하면 O(N)으로 최적화를 시킬 수 있습니다.