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

16434번: 드래곤 앤 던전

 

문제

용사는 공주를 구하기 위해 무시무시한 용이 있는 던전으로 향하기로 하였습니다. 우선 용사는 용사 자신과 던전을 분석하였습니다.

용사에게는 세 종류의 능력치가 있습니다. 

• $H_{MaxHP}$ : 용사의 최대 생명력입니다. 이 값은 1이상이어야 하며 던전에 들어간 이후로 변하지 않습니다.
• $H_{CurHP}$ : 현재 용사의 생명력입니다. 던전에 들어가기 전 이 값은 용사의 최대 생명력 $H_{MaxHP}$와 같습니다. 이 값은 $H_{MaxHP}$보다 커질 수 없습니다.
• $H_{ATK}$ : 용사의 공격력입니다.

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

몬스터가 있는 방에 올 경우 다음과 같이 전투가 진행됩니다.

1. 용사의 공격력 $H_{ATK}$만큼 몬스터의 생명력을 깎습니다.
2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
3. 몬스터의 공격력만큼 용사의 생명력 $H_{CurHP}$를 깎습니다.
4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
5. 다시 1부터 진행합니다.

포션이 있는 방에 올 경우 포션을 마셔서 현재 용사의 생명력 $H_{CurHP}$가 일정량 회복되고 공격력 $H_{ATK}$도 일정량만큼 증가됩니다. 회복된 생명력이 최대 생명력 $H_{MaxHP}$보다 큰 경우 용사의 현재 생명력 $H_{CurHP}$가 최대 생명력 $H_{MaxHP}$와 같아집니다.

용사는 던전으로 향하기 전에 만반의 준비를 하고 있습니다. 용사는 수련을 하면 최대 생명력 $H_{MaxHP}$를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다.

용사는 $N$번 방에 있는 용을 쓰러트리기 위한 최소의 $H_{MaxHP}$를 여러분이 계산해주면 좋겠다고 합니다.

 

 

입력

첫 번째 줄에 방의 개수 $N$ (1 ≤ $N$  ≤ 123,456) 과 용사의 초기 공격력 $H_{ATK}$ (1 ≤ $H_{ATK}$ ≤ 1,000,000)가 주어집니다.

$i+1$번째 줄엔 $i$번째 방의 정보를 나타내는 세개의 정수 $t_i, a_i, h_i (t_i ∈ {1, 2}, 1 ≤ a_i, h_i  ≤ 1,000,000)$ 가 주어집니다. 

$t_i$가 1인 경우 공격력이 $a_i$이고 생명력이 $h_i$인 몬스터가 있음을 나타내고, $t_i$가 2인 경우 용사의 공격력 $H_{ATK}$를 $a_i$만큼 증가시켜주고 용사의 현재 생명력 $H_{CurHP}$를 $h_i$만큼 회복시켜주는 포션이 있음을 나타냅니다.

출력

용사가 $N$번째 방에 있는 용을 쓰러트리기 위한 최소의 $H_{maxHP}$를 출력합니다.

코드

import sys
input = sys.stdin.readline

n, atk = map(int, input().split())
rooms = []
for _ in range(n):
    # t == 1: 공격력이 a이고 생명력이 h인 몬스터
    # t == 2: 용사의 공격력을 a, 생명력을 h만큼 올려주는 포션
    t, a, h = map(int, input().split())
    rooms.append([t, a, h])

def simulate(curATK, maxHP):
    curHP = maxHP
    for t, a, h in rooms:
        # 몬스터
        if t == 1:  
            mATK = h//curATK    # 몬스터가 공격받을 수 있는 횟수
            curHP -= (mATK-1 if h%curATK == 0 else mATK) * a
            if curHP <= 0:  # 용사 사망
                return False
        # 포션
        else:       
            curATK += a
            curHP += h
            if curHP > maxHP:
                curHP = maxHP
    return True

start, end = 1, sys.maxsize
ans = 0
while start <= end:
    mid = (start + end) // 2
    if not simulate(atk, mid):
        start = mid + 1
    else:
        end = mid - 1 
        ans = mid
print(ans)

 

이분탐색을 이용하여 maxHP를 찾는다.

용사가 중간에 사망한다면 maxHP가 모자란 것이므로 start 값을 mid + 1로 갱신해주고 그렇지 않다면 ans에 현재 mid 값을 저장해주고 값을 줄여가며 최소의 maxHP를 찾는다.

 

처음에는 아래와 같이 풀었는데 시간 초과가 발생해서 simulate 함수 부분의 몬스터가 등장했을 때 부분의 코드를 수정하였다. 아래의 코드는 몬스터를 마주쳤을 때 while문을 돌아서 시간복잡도가 O($N^2$)이기 때문에 시간 초과가 발생한 것 같다.

import sys
input = sys.stdin.readline

n, atk = map(int, input().split())
rooms = []
for _ in range(n):
    # t == 1: 공격력이 a이고 생명력이 h인 몬스터
    # t == 2: 용사의 공격력을 a, 생명력을 h만큼 올려주는 포션
    t, a, h = map(int, input().split())
    rooms.append([t, a, h])

def simulate(curATK, maxHP):
    curHP = maxHP
    for i in range(n):
        t, a, h = rooms[i]
        if t == 1:  # 몬스터
            while h > 0:
                h -= curATK     # 용사 공격
                if h <= 0:      # 몬스터 사망
                    break
                curHP -= a      # 몬스터 공격
                if curHP <= 0:  # 용사 사망
                    return False
        else:       # 포션
            curATK += a
            curHP += h
            if curHP > maxHP:
                curHP = maxHP
    return True

start, end = 1, sys.maxsize
ans = 0
while start <= end:
    mid = (start + end) // 2
    if not simulate(atk, mid):
        start = mid + 1
    else:
        end = mid - 1 
        ans = mid
print(ans)