[C++] 백준(BOJ) - 16434 : 드래곤 앤 던전
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다.
용사에게는 세 종류의 능력치가 있습니다.
- HMaxHP : 용사의 최대 생명력입니다. 이 값은 1이상이어야 하며 던전에 들어간 이후로 변하지 않습니다.
- HCurHP : 현재 용사의 생명력입니다. 던전에 들어가기 전 이 값은 용사의 최대 생명력 HMaxHP와 같습니다. 이 값은 HMaxHP보다 커질 수 없습니다.
- HATK : 용사의 공격력입니다.
던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동 할 수 있습니다. 방에는 포션이 있거나 몬스터가 있는데 몬스터가 있을 경우 몬스터를 쓰러트려야지 다음방으로 이동 할 수 있습니다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있습니다.
몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.
- 용사의 공격력 HATK만큼 몬스터의 생명력을 깎습니다.
- 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
- 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
- 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
- 다시 1부터 진행합니다.
포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 HCurHP가 일정량 회복되고 공격력 HATK도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 HMaxHP보다 큰 경우 용사의 현재 생명력 HCurHP가 최대 생명력 HMaxHP와 같아집니다.
용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 HMaxHP를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.
용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 여러분이 계산해주면 좋겠다고 합니다.
입력
첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다.
i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 ≤ ai, hi ≤ 1,000,000) 가 주어집니다.
ti가 1인 경우 공격력이 ai이고 생명력이 hi인 몬스터가 있음을 나타내고, ti가 2인 경우 용사의 공격력 HATK를 ai만큼 증가시켜주고 용사의 현재 생명력 HCurHP를 hi만큼 회복시켜주는 포션이 있음을 나타냅니다.
출력
용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 출력합니다.
알고리즘
- 이분탐색
- 그리디
풀이
- 이분탐색
- N개의 방
- i -> i + 1로 진행
- 순서 변경 불가
- 공격
- 플레이어 공격
- 몬스터 공격
- 모듈러 연산을 통해 몬스터 공격 횟수 연산
- 회복
- 최대 체력을 넘는 회복 => 최대 체력만큼으로 고정 회복
- 최대 HmaxHP
- n = 123456 (약 10만) * 모두 포션 (100만) => 약 1000만
long long 타입
- n = 123456 (약 10만) * 모두 포션 (100만) => 약 1000만
- N개의 방
- 그리디
- 몬스터의 공격을 기반으로 플레이어의 최대 체력을 역추산
- (몬스터의 데미지) = (몬스터의 공격력) * (몬스터의 공격 횟수)
- 포션을 먹었을 때
- 포션을 먹어도 (현재체력 + 포션 먹은 값)이 (h_max)를 넘을 수는 없다
- 구한 히스토그램의 H_maxHp 값보다 + 1한 값이 정답
- 몬스터의 공격을 기반으로 플레이어의 최대 체력을 역추산
코드 1 : 이분탐색
// BOJ - 16434 : 드래곤 앤 던전
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e18;
ll n, h_atk, t, a, h, res = INF, l =1, r = 1e18, mid;
struct A
{
int t; int a; int h;
} arr[123466];
bool check(ll mid)
{
ll mxHp = mid;
ll init_atk = h_atk;
for (int i = 0; i < n; i++)
{
if (arr[i].t == 2)
{
mid = min(mxHp, mid + arr[i].h); // 포션 먹었을 때 최대 체력보다 높으면 최대치로 설정
init_atk += arr[i].a;
}
else
{
ll cnt = arr[i].h / init_atk + (arr[i].h % init_atk ? 1 : 0);
mid -= (cnt - 1) * arr[i].a; // (몬스터의 공격횟수) = (플레이어의 공격횟수 - 1)
}
if (mid <= 0) return false; // 용사의 죽음
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> h_atk;
for (int i = 0; i < n; i++)
{
cin >> arr[i].t >> arr[i].a >> arr[i].h;
}
while (l <= r)
{
ll mid = (l + r) / 2;
if (check(mid))
{
r = mid - 1;
res = mid;
}
else l = mid + 1;
}
cout << res << '\n';
return 0;
}
코드 2 : 그리디
// BOJ - 16434 : 드래곤 앤 던전
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e18;
ll n, h_atk, h_cur, h_max, t, a, h, res = INF, damage;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> h_atk;
for (int i = 0; i < n; i++)
{
cin >> t >> a >> h;
if (t == 1)
{
damage = a * (ceil((double) h / h_atk) - 1);
if (h_cur < damage)
{
h_max += damage - h_cur;
h_cur = 0;
}
else h_cur -= damage;
}
else
{
h_atk += a;
h_cur = min(h_cur + h, h_max); // 포션을 먹어도 (현재체력 + 포션 먹은 값)이 h_max를 넘을 수는 없다
}
}
cout << h_max + 1 << '\n';
return 0;
}
평가
- 이분탐색은 기본적으로
long long자료형 사용 - for문으로 구할 수도 있지만, 모듈러 연산을 통해 공격 횟수를 간단하게 구할 수 있다
- 구조체를 이용하여 다중 변수를 한번에 입력받을 수 있다
- 그리디 알고리즘을 활용해 매 입력이 들어올 때마다 플레이어 최대 체력의 값을 역추산하며 구하는 코드를 짤 수있다
