[백준 16434] 드래곤 앤 던전

 

 

이분탐색으로 풀었다.

1. MAXHP 로 사용할 임의 변수를 둔다.

2. Ti 에 따라 몬스터를 만나면 체력을 깎고 포션이면 체력과 공격력을 증가시킨다.

2-1. 몬스터랑 싸우는 도중 체력이 0이되면 실패하니 주의한다.

2-2. 몬스터의 체력 / 자신의 공격력이 0인지 아닌지에 따라 분기한다.

3. 반복하면서 최소의 MAXHP를 찾는다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int atk = sc.nextInt();
        int a[][] = new int[n][3];
        for(int i=0; i<n; i++) {
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
            a[i][2] = sc.nextInt();
        }
        
        long left = 0;
        long right = ((long)2 << 62) - 1;
        while(left <= right) {
            long mid = (left + right)/2;
            long satk = atk;
            long hp = mid;
            boolean alive = true;
            for(int i=0; i<n; i++) {
                if(a[i][0] == 1) {
                    if(a[i][2] % satk == 0) hp -= ((a[i][2] / satk) - 1) * a[i][1];
                    else hp -= (a[i][2] / satk) * a[i][1];
                    if(hp <= 0) {
                    alive = false;
                    break;
                }
                } else {
                    hp += a[i][2];
                    hp = hp > mid ? mid : hp;
                    satk += a[i][1];
                }
            }
            if(!alive) left = mid + 1;
            else right = mid - 1;
        }
        System.out.println(left);
    }
}