백준 16434 드래곤 앤 던전 Python 3

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

16434번: 드래곤 앤 던전

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ16434.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from math import ceil
def get_max_HP(N, s_atk, rooms):
    left = 1
    right = N*1000000000000
    while left <= right:
        mid = (left+right)//2
        soldier_HP = mid
        soldier_atk = s_atk
        dead = False
        for i in range(N):
            t, a, h = rooms[i]
            #몬스터 방
            if t == 1:
                cnt = ceil(h/soldier_atk)-1
                soldier_HP -= cnt*a
                if soldier_HP <= 0:
                    dead = True
            #포션 방
            else:
                soldier_HP += h
                if soldier_HP > mid: soldier_HP = mid
                soldier_atk += a

            if dead: break

        if dead:
            left = mid + 1

        else:
            answer = mid
            right = mid - 1
    return answer

input = sys.stdin.readline
N, s_atk = map(int, input().split())
rooms = list()
for _ in range(N):
    rooms.append(list(map(int, input().split())))
print(get_max_HP(N, s_atk, rooms))

---

최종 코드

N개의 방에 차례대로 이동하면서 몬스터를 죽일 수 있도록 용사의 MaxHP의 최솟값을 구하는 문제이다.

가능한 MaxHP의 범위는 1부터 N*1000000*1000000이다.

왜냐하면 N개의 방에 몬스터가 1마리도 없거나 존재하는 몬스터의 생명력이 용사의 공격력보다 작거나 같은 경우 등 용사의 HP가 소진될 일이 없을 수 있기 때문에 이러한 경우에는 최소 1 HP가 필요하다.

반대로 모든 방에 몬스터가 존재하는데 용사의 공격력이 1이고 몬스터의 공격력과 생명력은 1000000이라면 용사는 적어도 N*1000000*1000000만큼의 HP가 필요하다.

따라서 1~N*1000000*1000000 사이의 값을 탐색하면서 최소의 MaxHP를 구해야하기 때문에 로그 시간복잡도 내에서 탐색을 할 수 있는 이분 탐색을 적용해야 한다.

import sys
from math import ceil
def get_max_HP(N, s_atk, rooms):
	#용사의 생명력이 될 수 있는 범위 초기화
    left = 1
    right = N*1000000000000
    
    #이분 탐색
    while left <= right:
    	#mid를 용사의 최대 생명력으로 가정
        mid = (left+right)//2
        
        #던전으로 향한다
        #용사의 초기 HP는 최대 생명력으로 초기화
        soldier_HP = mid
        #용사의 초기 공격력은 입력으로 받아온 공력력으로 초기화
        soldier_atk = s_atk
        #용사의 생존 여부
        dead = False
        for i in range(N):
            t, a, h = rooms[i]
            #몬스터 방인 경우,
            if t == 1:
            	#몬스터가 죽기 직전까지 몇 번의 공격을 해야하는지 카운팅 -> 몬스터에게 용사가 먼저 공격을 하기 때문에 몬스타가 죽기 직전까지 용사의 생명력이 0이상인지만 판단하면 된다
                cnt = ceil(h/soldier_atk)-1
                soldier_HP -= cnt*a
                
                #용사가 죽은 경우, dead를 True로 바꿔준다
                if soldier_HP <= 0:
                    dead = True
                    
            #포션 방인 경우,
            else:
            	#용사의 생명력을 회복시킨다
                soldier_HP += h
                #용사의 최대 생명력 만큼만 회복이 가능하다
                if soldier_HP > mid: soldier_HP = mid
                
                #용사의 공격력이 증가된다
                soldier_atk += a
			
            #용사가 죽은 경우, 용사의 최대 생명력을 높여야하기 때문에 던전에서 빠져나온다
            if dead: break
		
        #던전에서 용사가 죽은 경우, 최대 생명력을 높이기 위해 left 범위를 늘려준다
        if dead:
            left = mid + 1
		
        #던전에서 용사가 살아남은 경우, 최소의 최대생명력을 구하기 위해 right 범위를 줄인다 
        else:
        	#answer 값 갱신
            answer = mid
            right = mid - 1
    return answer

input = sys.stdin.readline
N, s_atk = map(int, input().split())
rooms = list()
for _ in range(N):
    rooms.append(list(map(int, input().split())))
print(get_max_HP(N, s_atk, rooms))

#시간복잡도 = O(log n), 공간복잡도 = O(n)