백준_16434_드래곤 앤 던전(python)

● 접근법

    - 입력에서 n의 최대 크기가 123,456인데 대략 최대 십이만 이라고 생각해보자. 시간 제한은 1초이고 파이썬으로 for문 여러개를 썼다가는 시간 초과가 발생할 것이 뻔하다. 그럼 어떻게 시간 안에 최소를 구해야 할까? 여기서 생각은 단순해진다. for문을 한 번만 써야한다. 그리고 여기서 어떻게 한 번에 minHP를 구해야 하지? 뒤에서 부터 가면 되지 않을 까라는 생각을 했지만 t가 2일 경우 공격력이 점차 증가해 몬스터를 빨리 물리치니 뒤에서부터 계산할 수 없다는 것을 깨닫는다. 그럼 남은 방법은 앞에서부터 출발하는 하나의 방법이 남는다. 

● 풀이법

1. 누적된 데미지, 공격력을 위한 변수 td, ta를 만든다. 

2. t가 1일 경우 td를 빼주고 매 반복마다 td의 최솟값을 갱신해준다.

3. t가 2일 경우에서 누적 데미지가 양수가 됐다면 0으로 초기화 해준다. (0으로 초기화 하는 이유는 우리는 최소한의 minHP를 구하는 것이 목표다. 만약 누적데미지가 -70 이었다고 해보자 그리고 다음 입력에서 + 75를해서 td가 5가 됐고 다음 입력에서 t가 1일떄 데미지를 -74를 입어 -69가 됐다고 가정하면 min값은 -74로 갱신 됐어야 했지만 전에 0으로 초기화를 해주지 않았기 때문에 아직도 -70으로 돼있을 것이고 용사는 71의 체력으로 던전에 들어갔다가 죽고 말 것이다.)

4. 마지막에 절댓값을 취한 후 + 1을 해주면 된다. 

 

● 코드

import sys
input = sys.stdin.readline

n,damage = map(int,input().split())

td = 0
ta = damage
answer = float("inf")
for i in range(n):
    t,a,h = map(int,input().split())
    if t == 1:
        if h % ta == 0:
            td -= (h // ta - 1) * a
        else:
            td -= h // ta * a
        answer = min(td, answer) # 매번 answer을 갱신해준다.
    else:
        ta += a
        td += h
        if td > 0 :
            td = 0
answer = min(td, answer)
print(abs(answer) + 1)

 

● 회고

막막해 하지 말자 하면 할 수 있다.