BOJ 16434

드래곤 앤 던전

문제출처

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)으로 최적화를 시킬 수 있습니다.