[백준 16434 파이썬] 드래곤 앤 던전 (골드4, 이분탐색)

알고리즘 유형 : 이분 탐색
풀이 없이 스스로 풀었나요? : ❌

---

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

솔루션

1. 이분 탐색 범위를 1 ~ 최악의 경우(용사의 공격력이 1이고 모든 방의 몬스터의 공격력, 생명력이 1,000,000 인 경우)로 제한

2. 이분 탐색 시작

3. 용사의 체력이 mid일때 클리어 가능한지 살펴본다.

4. 클리어 성공 시 res에 mid 저장 후 mid + 1을 lt로 두고 다시 while문 반복

5. 클리어 실패 시 mid - 1을 rt로 두고 다시 while문 반복

6. 이분탐색 종료되면 결과 값인 res 출력

소스 코드

import sys

input = sys.stdin.readline


def clear_check(cur_atk, max_hp):
    cur_hp = max_hp
    for type, atk, hp in dungeons:
        if type == 1:  # 몬스터
            turn = hp // cur_atk if not hp % cur_atk else hp // cur_atk + 1  # A if not 조건 else B
            cur_hp -= atk * (turn - 1)
        else:  # 물약
            cur_atk += atk
            cur_hp += hp
            if cur_hp > max_hp:
                cur_hp = max_hp
        if cur_hp <= 0:  # 용사의 HP가 0이하라면 클리어 실패
            return False
    return True


if __name__ == "__main__":
    N, ATK = map(int, input().split())
    dungeons = []
    for _ in range(N):
        type, atk, hp = map(int, input().split())
        dungeons.append((type, atk, hp))

    lt, rt = 1, N * 1000000 * 1000000
    res = 0
    while lt <= rt:
        mid = (lt + rt) // 2
        if clear_check(ATK, mid):
            res = mid
            rt = mid - 1
        else:
            lt = mid + 1

    print(res)