[BOJ/백준] 16434 드래곤 앤 던전 파이썬

문제 링크 : https://www.acmicpc.net/problem/16434

16434번: 드래곤 앤 던전

 

이분 탐색으로 풀었다.

최대 HP는 모든 칸이 다 몬스터이고 모든 애들의 공격력과 체력이 1백만이라 했을 때

123456*1백만*1백만이다.

 

1~최대 HP까지에서 이분탐색으로 hp찾아보자.

hp를 선택했으니 시뮬레이션 돌려보자.

만약 돌린 결과가 False가 나온다면 선택한 hp로는 부족하다는 뜻이다.

그러므로 mid+1을 left로 수정하자.

 

근데 돌린 결과가 True라면 해당 hp로 충분하다는 뜻이므로 right를 mid로 수정하자.

mid+1이 아님에 주의하자. 최솟값을 찾아야 하므로 mid 보다 큰 애들은 볼 필요가 없다.

이렇게 이분탐색을 수행한다면 right가 최솟값이 되어 있을 것이다.

 

이제 현재 hp를 정하고 시뮬레이션해보자.

내가 몬스터를 잡을 때의 공격 횟수와

내가 몬스터에게 잡혔을 때 공격 횟수를 계산하자.

 

hp,at가 나의 체력, 공격력이고

h,a를 몬스터의 체력 공격력이라 했을 때 그 횟수는 아래처럼 구하면 된다.

 

ceil(h/at) : 내가 몬스터를 잡기 위해 때려야하는 횟수

ceil(hp/a) : 몬스터가 나를 잡기 위해 때려야하는 횟수

이때 ceil은 올림 연산이다.

 

만약 몬스터가 공격한 횟수가 나보다 작다면 나는 몬스터에게 진것이니 해당 hp로는 부족하다.

근데 만약 횟수가 똑같거나 내가 더 적다면 hp - (그 횟수-1)*a 하면 전투 후 나의 hp가 나온다.

-1한 이유는 내가 먼저 공격을 하기 때문에 몬스터는 나보다 1번 덜 공격한다.

이를 모든칸에서 수행하면 전투 결과를 얻을 수 있다.

 

from sys import stdin
import math

input = stdin.readline

n,att = map(int, input().split())
board = []

for _ in range(n):
    t,a,h = map(int, input().split())
    board.append((t,a,h))
def solv():
    left = 1
    right = 123456*1000000*1000000

    while left < right:
        hp = (left+right)//2
        if simul(hp):
            right = hp
        else:
            left = hp+1
    print(right)
def simul(hp):
    at = att
    max_hp = hp
    for t,a,h in board:
        if t == 1:
            m_cnt = math.ceil(h/at)
            a_cnt = math.ceil(hp/a)
            if m_cnt <= a_cnt:
                hp -= (m_cnt-1)*a
            else:
                return False
        else:
            at += a
            hp += h
            if hp > max_hp:
                hp = max_hp
    return True

solv()