[boj : 16434] 드래곤 앤 던전

[문제] : https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

[분류] :이분탐색(파라메트릭)

 

[조건] :

1)용사의 공격력(atk)이 주어진다.

2)N만큼의 방이 존재하며 a가 1일때 몬스터와 용의 공격력와 체력이 주어진다.용사가 이방에 들어가서 몬스터를 잡아야 다음 방으로 넘어갈 수 있음.(이때 몬스터를 t번의 공격으로 잡을 수가 있다면 몬스터는 t-1번의 공격밖에 못하게 됩니다.용사가 t번째 공격했을때 몬스터는 죽게 되니깐요.)

a가 2일때 포션이 있으며 용사의 공격력을 상승,체력을 회복 시켜준다.(만약 회복할때 용사의 최대 체력을 초과 하게된다면 최대 체력이 한계 입니다.)

3)용사의 체력이 0 이하가 되면 처음부터 다시 시작

 

[구현방법]:

이분탐색(파라메트릭) 문제입니다. 전 문제 유형을 파악하기도 어려웠습니다.djm03178 님의 말씀에 의하면 "문제에서 '최소 얼마'를 구해야 한다는 말이 나오고 그 범위가 광대한 걸 본 순간부터 얼마 이상이면 항상 성립하는 구조라면 이분 탐색으로 그 위치를 찾을 수 있다고 생각할 수 있다."라고 합니다.(감사합니다)

결론은 이런 특징을 항상 기억해 놓고 있으며 문제를 많이 풀면서 경험을 쌓는 방법밖에는 없습니다.(저도 계속 진행중,,)

범위를 체크할 left,right 를 임의적으로 선언해 주고 (이때 수가 크니 long long 형을 사용해야 합니다.) mid = (left+right)/2 를 최대 체력으로 잡고 진행하면 됩니다. 만약 이 체력이 0이하가 되면 낮게 설정되었다는 뜻이므로 left = mid+1 을 체력이 0 이상이면 높게 설정되었다는 뜻이므로 right=mid-1 로 해주면 됩니다.그리고 left가 right 보다 커지면 그때 정답을 도출해 내면 됩니다.

 

[소스] :

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
typedef struct Info {
    ll t, a, h;
    Info(ll t, ll a, ll h){
        this->t = t;
        this->a = a;
        this->h = h;
    }
}info;
vector<info> v;
 
int main()
{
    ll n, atk;
    ll ans;
    cin >> n >> atk;
 
    ll a, b,c;
    for(int i=0;i<n;i++)
    {
        cin >> a >> b>>c;
        v.push_back(info(a,b,c));
    }
    ll left = 0, right = LLONG_MAX;//right = LLONG_MAX;
 
    ll t_atk;
    while (left <= right)
    {
        t_atk = atk;        
        ll mid = (left + right) / 2;
        ll tmp = mid;
        for (int i = 0; i < n; i++){
            if (v[i].t == 1) {
                ll x = (v[i].h % t_atk);
                if (x == 0)
                    tmp -= (v[i].h / t_atk - 1)*v[i].a;
                else
                    tmp -= (v[i].h / t_atk)*v[i].a;
            }            
            else {
                t_atk += v[i].a;
                tmp += v[i].h;
                if (tmp >= mid)
                    tmp = mid;
            }
            if (tmp <= 0)
                break;
        }
        if (tmp > 0) {
            ans = mid;
            right = mid - 1;
        }
        else             
            left = mid + 1;
        
    }
    cout << ans;
    return 0;
}

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다