백준 16434: 드래곤 앤 던전

문제 요약

용사가 던전의 몬스터와 포션이 있는 모든 방을 통과하고, 마지막 용을 클리어하기 위한 최소의 maxHP를 구하는 문제

문제 분류

• 구현
• 이분 탐색

문제 풀이

maxHP를 이분탐색을 통해 구하면 되는 문제이다.

최소값은 1, 최대값은 long long int의 최대값으로 대입해주었고,

이분탐색의 결과 중 가능한 경우를 ans변수에 저장하는 것도 주요 아이디어이다. (단순히 while문 종료 후 Left 혹은 Right를 출력하는 것이 아니라)

풀이 코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long int l = 1, r = 9223372036854775807, mid, hp, atk, satk, m_hp, ans;
long long int ary[123457][3];

int main()
{
	int N;

	cin >> N >> atk;
	for (int i = 0; i < N; i++)
		scanf("%lld%lld%lld", &ary[i][0], &ary[i][1], &ary[i][2]);
	while (r >= l) {
		mid = (l + r) / 2;
		hp = mid;
		satk = atk;
		for (int i = 0; i < N; i++) {
			if (ary[i][0] == 1) {
				m_hp = ary[i][2] - satk;
				if (m_hp > 0) {
					hp -= (m_hp / satk) * ary[i][1];
					if (m_hp % satk > 0) hp -= ary[i][1];
				}
				if (hp <= 0) break;
			}
			else {
				satk += ary[i][1];
				hp += ary[i][2];
				if (hp > mid) hp = mid;
			}
		}
		if (hp <= 0) l = mid + 1;
		else {
			r = mid - 1;
			ans = mid;
		}
	}
	printf("%lld", ans);
	
	return 0;
}