[ 16434 ] [ 이진 탐색 ] 드래곤 앤 던전

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

16434번: 드래곤 앤 던전

---

풀이 과정

---

1. 최소 생명력을 1, 최대 생명력을 넉넉하게 10^16정도 잡아두고 최소를 찾는 것이므로 크다고 문제가 되는건 아니니까 이진 탐색을 진행한다. 
2. 범위의 중간값을 기준으로, 던전을 끝까지 클리어할 수 있는지 시뮬레이션 해본다.
   1. 몬스터인 경우, 몬스터의 체력 // 현재 공격력만큼 전투를 해야 한다.
   2. 따라서 몬스터의 공격력 x (몬스터의 체력 // 현재 공격력) 만큼 현재 hp에서 빼주면 된다. 단, 이 때 나누어 떨어지는 경우는 전투가 딱 맞춰서 끝나는 경우이므로 몬스터의 공격력 x (몬스터의 체력 // 현재 공격력 - 1)을 빼준다.
   3. 포션인 경우는 공격력은 그냥 올려주고, 체력의 경우 최대 체력까지만 올라갈 수 있도록 처리해 준다.
3. 던전의 끝까지 클리어할 수 있다면 최대 체력의 최솟값을 구해야 하므로 정답 저장 후 왼쪽 구간을 진행하고, 클리어할수 없다면 최대 체력을 올려야 하므로 오른쪽 구간을 진행한다.
4. 정답을 출력한다.

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()

N, Hatk = map(int, input().split())

dungeons = [list(map(int, input().split())) for _ in range(N)]

left = 1
right = int(10e16)
answer = 0
while left <= right:
    mid = (left + right) // 2
    current_HP = mid
    current_ATK = Hatk
    status = True
    for dungeon in dungeons:
        t, a, h = dungeon
        if t == 1:
            step = h // current_ATK
            if h % current_ATK == 0:
                step -= 1
            current_HP -= a * step
            if current_HP <= 0:
                status = False
                break
        elif t == 2:
            current_HP = min(current_HP+h, mid)
            current_ATK = current_ATK + a
        
    if status:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer)