[Python][백준 16434][이분 탐색] 드래곤 앤 던전 - 컴도리돌이

반응형

16434번: 드래곤 앤 던전

---

풀이 과정

1. 알고리즘 분류로 이분 탐색으로 되었지만 단순 구현으로 풀 수 있다. 하지만 오랜만에 이분 탐색으로 문제를 해결하였다.

 

2. 보통 이분 탐색에서는 target을 뭐로 정해야하는지 감을 잡기 힘들 때가 많다. 그럴 때는 물어보는 것(HmaxHp)을 target으로 잡아주면 좋다. 아님 말고 😊

 

3. 필자는 최소 hp 값을 찾기 위하여 hp을 target으로 잡았다. left = 0, right = sys.maxsize으로 설정하여 중간 값(mid)가 방을 완전히 돌 수 있으면 해당 mid 값을 answer에 저장하고 right 값을 mid-1으로 설정하여 다시 이분 탐색을 하였다.

 

4. binarysearch 함수에서는 문제에서 요구하는데로 단순 구현을 시키면 된다.

•   4-1)  t 가 1일 때 : 몬스터를 얼마만에 잡을 수 있는지 용사의 공격력으로 나눠준다. 만약 나머지가 0이면 용사가 먼저 몬스터를 죽일 수 있기 때문에  (몬스터 Hp / 용사의 공격력  - 1) x 몬스터의 공격력만큼 hp를 깎아준다. 나머지가 0이 아니면 온전히 (몬스터 Hp / 용사의 공격력 ) x 몬스터의 공격력만큼 hp를 깎아 준다.
• 4-2)  t가 1이 아닐 때 : 포션을 의미하기 때문에 용사의 hp를 포션 hp만큼 더해준다. 여기서 주의할 점은 용사의 maxHp를 넘으면 안 되기 때문에 더해준 값과 maxHp 둘 중에 min 값으로 할당해줘야 한다. 공격력을 상관없이 더해주면 된다.
• 4-3) 주어진 용사의 hp가 0이 될 경우 False로 반환을 시켜줘서 이분탐색의 left 값을 mid +1로 설정해서 다시 이분 탐색을 시켜준다.

---

풀이 코드 1(이분 탐색)

import sys; input = sys.stdin.readline
n,atk = map(int,input().split())
room = [list(map(int,input().split())) for _ in range(n)]
left,right,answer = 0,sys.maxsize,0

def binarySearch(atk,hp,maxHp) :
  for t,a,h in room :
    if t == 1 : hp = hp -( (h // atk -1 )* a ) if h % atk == 0  else hp - (h // atk * a)
    else : hp = min(maxHp,hp + h);atk += a
    if hp <= 0 : return False
  return True
  
while left <= right :
  mid = (left + right) // 2
  if binarySearch(atk,mid,mid) : right = mid - 1 ; answer = mid
  else : left = mid + 1
print(answer)

 

풀이 코드 2 (단순 구현 - n이 작기 때문에 굳이 이분탐색 x)

import sys; input = sys.stdin.readline
n,atk = map(int,input().split())
maxHp,ans = 0,0
for t,a,h in [list(map(int,input().split())) for _ in range(n)] :
  if t == 1 : maxHp = maxHp - (h // atk - 1) * a if h % atk == 0 else maxHp - (h // atk * a)
  else : atk += a ; maxHp = min(maxHp + h, 0)
  ans = min(ans,maxHp)
print(-ans+1)