문제
용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다.
용사에게는 세 종류의 능력치가 있습니다.
- H_MaxHP : 용사의 최대 생명력입니다. 이 값은 1이상이어야 하며 던전에 들어간 이후로 변하지 않습니다.
- H_CurHP : 현재 용사의 생명력입니다. 던전에 들어가기 전 이 값은 용사의 최대 생명력 HMaxHP와 같습니다. 이 값은 HMaxHP보다 커질 수 없습니다.
- H_ATK : 용사의 공격력입니다.
던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동 할 수 있습니다. 방에는 포션이 있거나 몬스터가 있는데 몬스터가 있을 경우 몬스터를 쓰러트려야지 다음방으로 이동 할 수 있습니다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있습니다.
몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.
- 용사의 공격력 HATK만큼 몬스터의 생명력을 깎습니다.
- 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
- 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
- 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
- 다시 1부터 진행합니다.
포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 HCurHP가 일정량 회복되고 공격력 HATK도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 HMaxHP보다 큰 경우 용사의 현재 생명력 HCurHP가 최대 생명력 HMaxHP와 같아집니다.
용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 HMaxHP를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.
용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 여러분이 계산해주면 좋겠다고 합니다.
입력
- 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ H_ATK ≤ 1,000,000) 가 주어집니다.
- i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 tᵢ, aᵢ, hᵢ (tᵢ ∈ {1, 2}, 1 ≤ aᵢ, hᵢ ≤ 1,000,000) 가 주어집니다.
- tᵢ가 1인 경우 공격력이 aᵢ이고 생명력이 hᵢ인 몬스터가 있음을 나타내고, tᵢ가 2인 경우 용사의 공격력 H_ATK를 aᵢ만큼 증가시켜주고 용사의 현재 생명력 H_CurHP를 hᵢ만큼 회복시켜주는 포션이 있음을 나타냅니다.
출력
- 용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 출력합니다.
예제
입력 1
3 3
1 1 20
2 3 10
1 3 100
출력 1
49
입력 2
1 1
1 1000000 1000000
출력 2
999999000001
풀이
import math
N, H = map(int, input().split())
dungeons = [list(map(int, input().split())) for _ in range(N)]
lt = 1
rt = 1
for t, a, h in dungeons: # 총 받는 데미지의 합을 rt로 정함
if t == 1:
rt += math.ceil(h / H) * a
rst = 0 # 결과 담을 변수
while lt <= rt: # 이분탐색 시작
mid = (lt + rt) // 2 # mid 정의. 초기 생명력
attack = H # 현재 공격력과 생명력
hp = mid
for t, a, h in dungeons:
if t == 1: # 몬스터 있는 경우
# 싸우는 횟수.
numOfFight = min(math.ceil(h / attack), math.ceil(hp / a))
# 싸운 만큼 서로의 생명력 깎음.
h -= numOfFight * attack
hp -= numOfFight * a
# 용사가 이긴 경우
if h <= 0:
# 용사가 먼저 때리기에 이겼으면 마지막에는 생명력이 깎일 일이 없으므로 다시 회복
hp += a
continue
# 용사가 진 경우
if hp <= 0:
break
else: # 몬스터가 아닌 포션이 있는 경우
attack += a # 공격력 증가
hp += h # 생명력 회복
if hp > mid: # 회복된 생명력이 최대 생명력보다 크면
hp = mid # 최대 생명력에 맞춤
else: # 용사가 무사히 모두 무찌른 경우
rt = mid - 1 # 생명력이 남기에 rt값을 줄임
rst = mid # 값 저장
if hp <= 0: # 용사가 죽은 경우
lt = mid + 1 # 생명력이 부족하기에 lt값 키움
print(rst)