[백준] 16434번: 드래곤 앤 던전 | Python 파이썬 풀이

알고리즘 분류: 이분 탐색

 

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

16434번: 드래곤 앤 던전

 

처음 풀이는 이분 탐색으로 풀었습니다. 

 

첫 번째 풀이😊

import sys
from math import ceil
input = sys.stdin.readline

n, power = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]

left, right, result = 1, 123455876544000001, 123455876544000001
while left <= right:
    hp = mid = (left + right) // 2
    atk = power
    for t, a, h in info:
        if t == 1:
            hp -= (ceil(h / atk) - 1) * a
            if hp < 1:
                break
        else:
            atk += a
            hp += h
            if hp > mid:
                hp = mid
    if hp > 0:
        right = mid - 1
        result = min(result, mid)
    else:
    	left = mid + 1
    
print(result)

 

하지만 이분 탐색 그대로 푸는 건 시간이 너무 많이 나와서 두 번째 풀이는 이분 탐색을 사용하지 않고 풀었습니다.

 

두 번째 풀이 - 틀림😭😭😭 (뒤에 정답 코드 나옵니다)

import sys
from math import ceil
input = sys.stdin.readline

n, atk = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]
hp=0
for t, a, h in info:
    if t == 1:
        hp += (ceil(h / atk) - 1) * a
    else:
        atk += a
        hp -= h
        if hp < 0:
            hp = 0

print(hp + 1)

 

아무리 생각해도 맞는 것 같은데....!!! 도대체 왜 틀렸을까... 고민하다가 백준 질문 게시판을 봤습니다.

그리고 찾은 반례 입니다. 제 코드에서는 49가 나오는데 정답은 61입니다.

8 3 
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
1 1 31
2 3 70
1 3 100

여기를 누르면 백준 반례 게시글로 이동합니다.

 

 

정답 코드😍

import sys
from math import ceil
input = sys.stdin.readline

n, atk = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]
hp, max_hp = 0, 0
for t, a, h in info:
    if t == 1:
        hp += (ceil(h / atk) - 1) * a
    else:
        max_hp = max(max_hp, hp)
        atk += a
        hp -= h
        if hp < 0:
            hp = 0

print(max(max_hp, hp) + 1)