백준 BOJ 16434 - 드래곤 앤 던전

아니 이거 왤케 역겨움;;

 

https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

Hmaxhp 를 파라메트릭 서치해주면 된다.

숫자 범위부터 해서 상당히 역겨운 문제인데

몇가지 들어보자면

1. 나이브하게 싸우는걸 시뮬레이션하면 TLE를 받음

2. 파라메트릭 최고범위가 123456 * 1e12 <= 2e18 이라는 큰 사이즈임.

 

2번때문에 그냥 LLONG_MAX를 박았다가는 바로 산술오버플로우가 나면서 맞왜틀을 하니

조심하도록 하자.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long ull;
int N, Hatk;

ll roomt[198765] = {0};
ll rooma[198765] = {0};
ll roomh[198765] = {0};

/*
 * Hmaxhp 파라메트릭. 
 * Hmaxhp 가 longlong범위인듯.
 * 방이 1e5개밖에 안되서 그냥 O(N)으로 탐색해도 될듯하다. 
 * Hmaxhp의 최대값은 용사공격력 1 적공격/체력둘다 1e6인 케이스
 * 이러면 1e6*1e6이니까 1e12? 가 최대인듯. 
 * 근데 이제 방수 123456개니까 실제로는 1e17을 살짝 넘는 숫자네요
 * 1e18 박으면 될거라 희망중. 
 */
 
ll search(ll s, ll e){ // mid -> Hmaxhp
	ll mid = (s+e)/2;
	if(s>e) return s;
	
	ll Hmaxhp = mid;
	ll Hcurhp = mid;
	ll Hcuratk = Hatk;
	
	bool survflag = true;
	for(ll i=1; i<=N; i++){
		if(roomt[i] == 1){
			ll tmp = roomh[i] % Hcuratk;
			
			if(tmp) Hcurhp -= (roomh[i] / Hcuratk) * rooma[i];
			else    Hcurhp -= (roomh[i] / Hcuratk -1) * rooma[i];
			
			/*ll enemyh = roomh[i];
			ll enemya = rooma[i];
			//printf("%llu %llu %llu %llu\n", Hcurhp, Hcuratk, enemyh, enemya);
			
			while(enemyh>0 && Hcurhp>0){
				enemyh -= Hcuratk;
				if(enemyh<=0ll) break;
				
				Hcurhp -= enemya;
				if(Hcurhp<=0ll){
					survflag = false;
					goto end;
				}
			}*/
		}
		
		if(roomt[i] == 2){
			Hcurhp = min(Hmaxhp, Hcurhp + roomh[i]);
			Hcuratk += rooma[i];
		}
		
		if(Hcurhp <= 0){ survflag = false; break; }
	}
	
	end:
	if(survflag) return search(s,mid-1);
	else         return search(mid+1,e);
}

int main(){
	cin >> N >> Hatk;
	for(int i=1; i<=N; i++){
		cin >> roomt[i] >> rooma[i] >> roomh[i];
	}
	cout << search(1,2e18);
	return 0;
}

시간아껴보겠다고 넣은 저 수식 간단히 설명해보자면

그냥 공격횟수를 (적 체력 / 아군 공격력)으로 단순화한 다음에

그 횟수만큼 공격받았다고 퉁치는 수식이다.

저렇게하고나면 체력이 0 아래로 떨어지는 경우가 생기니까

아래에서 따로 케이스 구분해서 탈출시켜줘야 함.

추가+

나는

https://blog.naver.com/kks227/220777333252

이분 탐색(Binary Search) (수정 2019-02-15)

님 추천문제를 밀고있어서 파라메트릭을 썼지만

정해가 원래 그리디 알고리즘을 이용한 역산인듯하다.

이러면 쉽다고함.