[맞음] 백준 16434 드래곤앤던전 // 매개변수 탐색, long long, 선빵

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

* 풀이

• 어려웠던점
  • long long일때, en값을 정하는부분
    • LLONG_MAX 를활용 or 1e18로 해도됨
  • 용사가 선빵을 때린다는점
    • n회 공격이 필요한경우, n-1회만 맞으면됨
    • n번째 공격에서는 몹이 죽어서 공격을 받지 않음
    • 여기서 용사가 공격받지 않는다는 사실을 추론해내야함.

화살표로 공격순서를 시각화하는것도 좋은 방법

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

struct A {
   ll t,a,h;
};

ll n,atk;
ll ret;
vector<A> v;

//최대피가 x일때, 되는지
bool go(ll x, ll atk) {
   ll tmp=x; //초기 최대피
   for(int i=0;i<n;++i) {
      if(v[i].t==1) {
         ll cnt=-1;
         cnt+=v[i].h/atk;
         if(v[i].h%atk) cnt++;
         // x -= cnt*v[i].a; //몹 공격력 * 공격횟수만큼 피깍기
         // 용사가 n번 공격해야 몬스터를 잡을 수 있다면, 용사가 공격을 받는 횟수는 n-1번이면 충분합니다.
         // 용사가 먼저 공격하고, 그 순간 몬스터가 죽었다면 용사는 공격받지 않기 때문입니다.
         if(x - cnt*v[i].a <=0 ) {
            // cout<<x<<"\n";
            // cout<<cnt*v[i].a<<"\n";
            return false;
         }
         x -= cnt*v[i].a; // 실제 체력 감소
      }
      else if(v[i].t==2) {
         atk+=v[i].a;
         x+=v[i].h;
         if(x>tmp) x=tmp; //최대 hp 초과 불가능
      }
   }
   return true;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);


   cin>>n>>atk;
   for(int i=0;i<n;++i) {
      ll t,a,h;
      cin>>t>>a>>h;
      v.push_back({t,a,h});
   }

   ll st=1;
   ll en = LLONG_MAX;
   while(st<=en) {
      ll mid = (st+en)/2;
      
      if(go(mid, atk)) {
         // cout<<"됨 "<<st<<" "<<mid<<" "<<en<<"\n";
         ret=mid;
         en=mid-1;
      }
      else {
         // cout<<"안됨 "<<st<<" "<<mid<<" "<<en<<"\n";
         st=mid+1;
      }
   }

   cout<<ret;
   
}

 

* 큰돌코드

• 로직은 같지만, 간결화

#include<bits/stdc++.h>
using namespace std;
#define co(a) cout << a << "\n";
typedef long long ll;      
ll n, attack, t[140005], a[140005], h[140005];
void fastIO(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}   
bool check(ll mid){
	ll init_hp = mid;
	ll init_attack = attack;  
	for(int i = 0; i < n; i++){
		if(t[i] == 2){
			mid = min(init_hp, mid + h[i]);
			init_attack += a[i];
		}else{
			ll div = h[i] / init_attack + (h[i] % init_attack ? 1 : 0);
			ll attack_Cnt = div - 1; 
		//	cout << "ATTACK : " << attack_Cnt * a[i] << "\n";
			mid -= attack_Cnt * a[i];
		}  
		//cout << mid << " ";
		if(mid <= 0) return false;
	}
	return true; 
}
int main(){ 
	fastIO();
	cin >> n >> attack; 
	ll init_lo = 1; 
	for(int i = 0; i < n; i++){
		cin >> t[i] >> a[i] >> h[i]; 
	}  
	ll lo = 1, hi = 1e18 + 4, ret; 
	while(lo <= hi){
		ll mid = (lo + hi) / 2; 
		if(check(mid)){
			hi = mid - 1; 
			ret = mid;
		}else lo = mid + 1; 
	}
	co(ret) 
	return 0;
}