[백준 16434] - Python

• 취알스 4주차 정렬, 이분탐색 - 4/5

16434 드래곤 앤 던전

이분탐색으로(0~long max) 용사의 체력을 찾아나가면 시간초과 발생함.

용사가 선공이기 때문에 용사가 n번 때려서 몬스터가 죽는다면 그 동안 몬스터에게 n-1번의 데미지를 맞는다. 이걸 고려하여 각 방에서 필요한 용사의 체력을 구한다. O(N)의 시간복잡도로 문제를 풀 수 있음.

import sys
n, atk = map(int, sys.stdin.readline().split())
dungeon=[[] for i in range(n)]
maxHP, curHP, damage = 0, 0, 0
for i in range(n):
    t, a, h = map(int, sys.stdin.readline().split())
    if t==1: # 몬스터방
        temp = h%atk
        if temp == 0:
            damage = -(a * (h // atk - 1))
        else:
            damage = -(a * (h // atk))
    else: # 포션방
        atk += a
        damage = h
    curHP += damage
    if curHP > 0:
        curHP = 0 # 풀피일 때 포션먹는 경우
    maxHP = max(maxHP, abs(curHP))
print(maxHP+1)

예제 1에서 던전을 도는 과정을 표로 나타내보았다.