[백준][python]16434 드래곤앤던전

문제

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

소스코드

import sys
import math

if __name__ == "__main__":
    n,atk = map(int,input().split())
    room = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

    max_hp = 0
    l,r = 1, sys.maxsize

    while l <= r:
        mid = (l+r) // 2

        cur_hp = mid
        cur_atk = atk

        for ro in room:
            t,a,h = ro
            if t == 1:
                cur_hp -= (math.ceil(h / cur_atk) - 1) * a
                if cur_hp <= 0:
                    break

            elif t == 2:
                cur_atk += a
                cur_hp = min(mid, cur_hp+h)

            if cur_hp <= 0:
                break

        if cur_hp <= 0 : #용사가 죽었으면 생명력 높이기
            l = mid + 1
        else:  #용사가 살았으면 생명력 낮추기
            r = mid - 1
            max_hp = mid

    print(max_hp)

설명

이분탐색으로 최대 HP를 구하는 문제이다.

몬스터와 전투를 하는 부분을 while 문으로 구현하게 되면 시간초과가 발생한다.

전투 과정을 경우의 수로 정의해서 구현하면 시간초과 문제를 해결할 수 있다.

 

                cur_hp -= (math.ceil(h / cur_atk) - 1) * a
                if cur_hp <= 0:
                    break

몬스터가 죽는 경우는 상관없기 때문에 구하지 않아도 된다.

중간에 누가 죽어서 break되는 부분을 생각하지 않고 전투 전체를 놓고 최종 결과만 생각한다.

 

(몬스터의 체력 / 용사의 공격력) 에서 올림 처리를 해주면 총 용사가 공격하는 횟수이다. 

• 만약 몬스터 체력이 10이고 용사의 공격력이 3이면 3.5 회 공격하는데 이는 4회 공격하는거랑 같다.

여기서 1을 빼주면 몬스터가 용사를 공격하는 횟수가 된다. 

• 용사가 먼저 공격을 하기 때문이다.
• 몬스터와 용사가 체력과 공격력이 동일하다고 가정하면, 몬스터가 먼저 죽기 때문에 용사는 -1 번을 뺀 공격을 받게 된다

몬스터가 공격할 횟수에서 몬스터의 공격력을 곱해주고 용사의 체력에서 빼면 전투를 마친 용사의 체력을 구할 수 있다.

몬스터가 더 쎈 경우는? 은 굳이 생각할 필요없다 그러면 마이너스 체력이 나오기 때문에 생각하지 않아도 된다.

그럼 몬스터의 체력이 마이너스가 나오는 경우는? 상관없다 용사의 체력이 마이너스인지 아닌지가 궁금한 사항이다.

 

또 이분탐색을 할 때 r 값을 최대한 크게 해줘야 모든 경우의 수를 다 포함해서 계산할 수 있다.