[이분탐색] 백준 16434. 드래곤 앤 던전

문제 링크

드래곤이랑 용사랑 싸울 건데, 용사가 이기기 위해 필요한 최소한의 hp가 얼마인가요?

1 try

import sys
sys.stdin = open('.//이분탐색//input2.txt', 'rt')

n, yp = map(int, input().split())
# n 방 개수
# pw 초기 공격력

print(n,yp)

# t a h 
# t = 1 몬스터, a 공격력, h 생명력
# t = 1 용사, a 공격력 증가, h 생명력 증가

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



def war(yp,yh):
    mp = 0
    mh = 0
    mid = yh
    for l in g:
        a = l[1]
        h = l[2]
        if l[0] == 1: # 몬스터 만남
            mp = a
            mh = h
            print('용사 hp', yh, end = ' / ')
            print('몬스터 hp', mh)
            print('용사 power', yp, end = ' / ')
            print('몬스터 power', mp)

            round = (mh // yp)
            yh = yh - (mp * round)

            if yh > 0:
                # yh += mp
                print(yh, 'y win')
                continue
            else:
                print(round, yh, mp)
                return False

        if l[0] == 2:  # 포션방
            yh = yh+h if yh+h <= mid else mid
            yp += a

    print(yh, 'y is winner')
    return True


low = yp # 초기 공격력보다는 크겠지 max가
# high = sum(sum(gg) for gg in g)
high = 10 ** 13
answer = 0
while low <= high:
    mid = (low+high)//2
    yh = mid
    if war(yp, yh) == False:
        low = mid + 1
    else:
        print(mid)
        answer = mid
        high = mid - 1
print(answer)

2try

def war(yp,yh):
    mp = 0
    mh = 0
    mid = yh
    for l in g:
        a = l[1]
        h = l[2]
        if l[0] == 1: # 몬스터 만남
            mp = a
            mh = h
            round = (mh // yp)
            yh -= mp * (round-1)

            if yh <= 0:
                return False

        if l[0] == 2:  # 포션방
            yp += a
            yh = min(yh+h ,mid)

    print(yh, 'y is winner')
    return True

최종 1

import sys
input = sys.stdin.readline

def war(yp,yh):
    mid = yh
    for l in g:
        a = l[1]
        h = l[2]
        if l[0] == 1: # 몬스터 만남
            mp = a
            mh = h
            round = (mh // yp)
            if mh % yp == 0:
                yh -= mp * (round-1)
            else:
                yh -= mp * (round)
            if yh < 1:
                return False
        else: # 포션방
            yp += a
            yh = min(yh+h ,mid)
    return True


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

low = 1
high = 10**17
# high = sum(max([gg[1]*gg[2]] for gg in g))

answer = 0
while low <= high:
    mid = (low+high)//2
    if war(yp, mid) == False:
        low = mid + 1

    else:
        high = mid - 1
        answer = mid

print(answer)

최종 2

import sys
input = sys.stdin.readline

def war(yp,yh):
    mid = yh
    for l in g:
        a = l[1]
        h = l[2]
        if l[0] == 1: # 몬스터 만남
            mp = a
            mh = h
            round = (mh // yp)
            mh -= round * yp
            yh -= round * mp
            if mh<=0:
                yh += mp 
            if yh < 1:
                return False
        else: # 포션방
            yp += a
            yh = min(yh+h ,mid)
    return True


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

low = 1
high = 10**17
# high = sum(max([gg[1]*gg[2]] for gg in g))

answer = 0
while low <= high:
    mid = (low+high)//2
    if war(yp, mid) == False:
        low = mid + 1

    else:
        high = mid - 1
        answer = mid

print(answer)

주의 사항

round (싸운 횟수)

최종 1의 경우, 나머지가 0이냐 아니냐로 round를 구분했다. 왜냐하면 나머지가 0이면 이미 전판에서 용사가 이긴 걸로 끝나고, 나머지가 있으면 한판 더 한거라, 용사 데미지에 차이가 있다.
최종 2의 경우, round를 고정하고 몬스터의 남아있는 체력이 0보다 작으면 이긴 것으로, 용사의 마지막 데미지를 회복시킨다. 0보다 크면 용사의 체력을 확인해서, 용사의 체력이 1보다 작으면 진 것으로 return False를 해준다.
둘 다 채점상으로는 정답이 맞다.

high 값을 정수의 최대값으로 해줬다.
high = sum(sum(gg) for gg in g)
high = sum(max(gg[0]*gg[1]) for gg in g)
등등으로 시도해봤는데, 틀렸다. 맞게 하려면 그래프를 돌면서 용사의 최소 체력과 몬스터의 최대 체력, 용사의 최소 공격력 을 이용해 식을 만들어 줘야 하는데, 이분탐색은 효과적으로 범위를 좁히기 때문에 굳이 그래프를 돌지 않고 문제에서 나올 수 있는 최대 숫자의 범위로 고정시켜 주어도 괜찮다.

탐색범위

방 개수 n의 최대값  * 몬스터 체력의 최대값  *  타격횟수의 최대값 (용사 공격력 1, 몬스터 공격력 최대) => 용사의 체력 최대
(123,456)                (1,000,000)                  (1,000,000)

즉, 10**(6+6+6) 쯤으로 잡아야 틀렸다고 나오지 않는다.

클릭하면, 원문의 블로그로 이동합니다.

r문제 풀고, 이해하는 데 걸린 시간.. 4시간.!

 

* 참고
https://devlibrary00108.tistory.com/148
https://intrepidgeeks.com/tutorial/boj-baijun-16334-dragon-and-copy-python

https://viyoung.tistory.com/188