[백준/16434/파이썬] 드래곤 앤 던전

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

16434번: 드래곤 앤 던전

Problem

• 용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 HMaxHP를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.
• 용사는 N번 방에 있는 용을 쓰러트리기 위한 최소의 HMaxHP를 여러분이 계산해주면 좋겠다고 합니다.

조건

• 던전은 총 N개의 방으로 이루어져 있고 i번째 방을 통해서만 i+1번째 방으로 이동 할 수 있습니다.
• 방에는 포션이 있거나 몬스터가 있는데 몬스터가 있을 경우 몬스터를 쓰러트려야지 다음방으로 이동 할 수 있습니다. N번째 방에는 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있습니다.

• 용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다. 용사에게는 세 종류의 능력치가 있습니다.
  • HMaxHP : 용사의 최대 생명력입니다. 이 값은 1이상이어야 하며 던전에 들어간 이후로 변하지 않습니다.
  • HCurHP : 현재 용사의 생명력입니다. 던전에 들어가기 전 이 값은 용사의 최대 생명력 HMaxHP와 같습니다. 이 값은 HMaxHP보다 커질 수 없습니다.
  • HATK : 용사의 공격력입니다.

• 몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.
• 1. 용사의 공격력 HATK만큼 몬스터의 생명력을 깎습니다.
  2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
  3. 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
  4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
  5. 다시 1부터 진행합니다.
• 포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 HCurHP가 일정량 회복되고 공격력 HATK도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 HMaxHP보다 큰 경우 용사의 현재 생명력 HCurHP가 최대 생명력 HMaxHP와 같아집니다.
• 첫 번째 줄에 방의 개수 N (1 ≤ N  ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK  ≤ 1,000,000) 가 주어집니다. ti가 1인 경우 공격력이 a[i]이고 생명력이 h[i]인 몬스터가 있음을 나타내고, ti가 2인 경우 용사의 공격력 HATK를 ai만큼 증가시켜주고 용사의 현재 생명력 HCurHP를 hi만큼 회복시켜주는 포션이 있음을 나타냅니다.
• i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 ≤ ai, hi  ≤ 1,000,000) 가 주어집니다. 

SOL

시뮬레이션으로 풀어도 되고, 블로그들을 찾아보니까 이분탐색으로도 가능한 문제이다.

 

시뮬레이션 

• 데미지를 계산해줘서,  최소한의 데미지로 던전을 클리어 할 수 있는 경우를 찾아주면 된다.
• O(N)으로 해결 가능! 

import sys
input = sys.stdin.readline

N, h_atk = map(int, input().split())
ROUND = []
for _ in range(N):
    ROUND.append(list(map(int, input().split())))

h_maxhp = 0
h_curhp = 0
h_damage = 0

for i in ROUND:
    if i[0] == 1:

        if i[2] % h_atk == 0:
            h_damage = -(i[1]*(i[2]//h_atk-1))
        else:
            h_damage = -(i[1]*(i[2]//h_atk))

    else:
        h_atk += i[1]
        h_damage = i[2]

    h_curhp += h_damage

    if h_curhp > 0:
        h_curhp = 0

    h_maxhp = max(h_maxhp, abs(h_curhp))


print(h_maxhp+1)

이분탐색

• 최대 HP를 줄였다가, 늘렸다가 하면서, 적절한 HP를 찾는다.

import sys
import math
input = sys.stdin.readline

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

start=1
end=1 # 최대 체력
for t,a,h in Dungeons:
    if t==1:
        end+=math.ceil(h/Hatk)*a
ans=0
while start<=end:
    #mid = 최대 HP
    mid = (start+end)//2
    #현재 용사의 스탯
    attack=Hatk
    Hcur=mid
    for t,Matk,Mhp in Dungeons:
        #몬스터와 만난경우
        if t==1:
            # 싸운 횟수는, 승부가 빠르게 난 쪽을 따라간다.
            turnOfFight=min(math.ceil(Mhp/attack),math.ceil(Hcur/Matk))
            # 싸운 횟수만큼 HP가 줄어든다.
            Mhp-=turnOfFight*attack
            Hcur-=turnOfFight*Matk
            #용사가 이기는 경우
            if Mhp<=0:
                #용사는 선빵을 치므로, 마지막 공격은 회복
                Hcur+=Matk
                continue
            #용사가 지는 경우
            if Hcur<=0:
                break
        #포션방
        else:
            attack+=Matk
            Hcur+=Mhp
            if Hcur>mid:
                Hcur = mid
    #용사가 무리없이 N번방까지 도달한 경우, 최대 체력을 줄인다.
    if Hcur>0:
        end=mid-1
        ans=mid
    else:
        start=mid+1

print(ans)