[백준] 16434 드래곤 앤 던전

문제

• 용사는 공주를 구하기 위해 던전으로 향한다.
• 던전은 N개의 방으로 이루어져 있고, i번째 방을 통해서만 i+1 번째 방으로 이동할 수 있다. 각 방에는 포션이나 몬스터가 있는데, 몬스터는 쓰러트려야지 다음 방으로 이동할 수 있다. N번째 방에 공주와 용이 있고, 용을 무찌르면 공주를 구할 수 있다.
  • 1 <= N <= 123,456
• 용사의 능력치
  • HmaxHP : 용사의 최대 생명력으로 값은 1 이상이고 던전에 들어간 이후로 변하지 않는다.
  • HcurHP : 용사의 현재 생명력으로 HmaxHP보다 커질 수 없다.
  • Hatk : 용사의 공격력
    • 1 <= Hatk <= 1,000,000
• 몬스터와의 전투
  
  • 용사와 몬스터가 번갈아가며 공격하고, 먼저 생명력이 0 이하가 되면 전투가 종료된다.
  • 공격은 용사 먼저한다.
• 포션
  • 용사의 생명력과 공격력이 증가된다.
• 용사가 N번 방에 있는 용을 쓰러트리기 위한 최소의 HmaxHP 계산하기

 

풀이

• 이분 탐색
• 시간 복잡도 : O(N log(sys.maxsize)) 이므로 가능
  • 최댓값 범위가 주어지지 않았으므로 sys.maxsize 를 사용

 

import sys
input = sys.stdin.readline

# 시나리오대로 던전 Go
def game(rooms, H_ATK, H_MAX):
    H_cur = H_MAX
    for t, a, h in rooms:
        # 몬스터
        if t == 1:      
            H_cur -= (h // H_ATK -1) * a if h % H_ATK == 0 else (h // H_ATK)  * a
            if H_cur <= 0:  # 용사가 죽는 경우
                return False
        # 포션
        elif t == 2:    
            H_cur = min(H_MAX, H_cur + h)   # H_MAX 이상이 될 수 없음
            H_ATK += a
    return True


# 입력 받기
N, H_ATK = map(int, input().split())
rooms = []
for _ in range(N):
    t, a, h = list(map(int, input().split()))
    rooms.append((t, a, h))

# 이분 탐색
s, e = 1, sys.maxsize
answer = 0
while s <= e :
    m = int((s+e) // 2)
    if game(rooms, H_ATK, m) :
        answer = m
        e = m-1
    else:
        s = m+1

print(answer)

 

References

• 백준 16434번
• 2023/04/21 오늘의 문제