[백준 16434] 드래곤 앤 던전 (JAVA)

문제

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

풀이

이분 탐색을 통해 Nlog(10^17)로 해결할 수 있으나 N으로도 해결할 수 있습니다.

모든 방을 클리어했을 때 용사가 받을 수 있는 최대 데미지를 계산하여 체력으로 바꿔주면 됩니다.
용사가 3번 공격해서 몬스터를 죽이면 용사는 (몬스터 공격력 * 2)의 피해를 입습니다.

포션은 현재 체력에서 마이너스로 계산해주고 0이하가 되지 않게 합니다.
받은 데미지 : 20, 포션 : 15 -> 받은 데미지 : 5
받은 데미지 : 20, 포션 : 30 -> 받은 데미지 : 0

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        long soldierAttack = Long.parseLong(st.nextToken());
        long soldierCurHP = 0, soldierMaxHp = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int attack = Integer.parseInt(st.nextToken());
            int hp = Integer.parseInt(st.nextToken());

            if (type == 1) {
                soldierCurHP += attack * ((hp / soldierAttack) - (hp % soldierAttack != 0 ? 0 : 1));
                soldierMaxHp = Math.max(soldierMaxHp, soldierCurHP);
            } else {
                soldierAttack += attack;
                soldierCurHP = Math.max(soldierCurHP - hp, 0);
            }
        }

        soldierMaxHp++;

        System.out.println(soldierMaxHp);
        br.close();
    }
}