백준 드래곤 앤 던전(16434)

드래곤 앤 던전

1. 힌트

1) 최대 생명력이 얼마인지를 알면 용사가 용을 쓰러트릴 수 있을지 여부는 $O(N)$의 연산을 통해서 알 수 있습니다. 만약 $x$의 HP로 용을 쓰러트리는데 성공했다면 $x + 1$의 HP로도 당연히 용을 쓰러트릴 수 있습니다. 여기서 이분 탐색을 사용할 수 있습니다.

2. 접근

힌트 참조

3. 구현

import sys
input = sys.stdin.readline
N, ATK = map(int, input().split())
S = [tuple(map(int, input().split())) for i in range(N)]

def f(x):
	atk = ATK; hp = x
	for i in range(N):
		t, a, h = S[i]
		if t == 1 :
			if (hp - 1) // a >= (h - 1) // atk : hp -= a * ((h - 1) // atk)
			else : return False
		else : atk += a; hp = min(hp + h, x)
	return True
	
lo = 0; hi = 123455876544123457
while lo + 1 < hi:
	mid = (lo + hi) // 2
	if mid != 0 and f(mid) : hi = mid
	else : lo = mid
print(hi)

1) 시간 복잡도

2) 테스트 케이스