[백준] 16434번 - 드래곤 앤 던전 (파이썬)

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

 

# 드래곤 앤 던전
N, A = map(int, input().split())
arr = []
for _ in range(N):
    type, atk, hp = map(int, input().split())
    arr.append((type, atk, hp))


def can_clear(curATK, maxHP):
    curHP = maxHP
    # 모든 방 탐색
    for type, atk, hp in arr:
        # 몬스터
        if type == 1:
            turn = hp//curATK if not hp % curATK else hp//curATK+1
            # 용사가 먼저 공격하므로 -1
            curHP -= atk * (turn-1)
        # 물약
        else:
            curATK += atk
            curHP += hp
            # 최대 회복은 maxHP까지만
            if curHP > maxHP:
                curHP = maxHP
        # 용사의 HP가 0이하라면 클리어 불가능
        if curHP <= 0:
            return False
    return True


result = 0
start, end = 1, N*int(1e6)*int(1e6)
while start <= end:
    mid = (start+end)//2
    if can_clear(A, mid):
        end = mid - 1
        result = mid
    else:
        start = mid + 1

print(result)

 

이분탐색
1. 방의 정보를 arr에 입력을 받는다.
2. 이분탐색 start = 1, end = N*1000000*1000000
    (최악의 경우 : 용사의 공격력이 1이고 모든 방(N)의 몬스터 HP와 공격력이 전부 최대치(100000)일 경우)
    - can_clear(공격력, 최대 HP) : 모든 방을 해당 최대 HP로 클리어할 수 있는지 boolean으로 리턴
3. result 출력