[Python] 백준 16434 드래곤 앤 던전

1. 문제 - 백준 16434 드래곤 앤 던전

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

 

💡알고리즘  - 구현, 이분탐색

• 우리는 용사가 N번째 방에 있는 용을 쓰러트리기 위한 최소의 생명력을 알아내야한다.
• 던전은 총 N개의 방으로 이루어져 있고, i번째 방을 통해서만 i+1 번째 방으로 이동할 수 있으며 몬스터가 있는 경우 반드시 쓰러뜨려야만 다음 방으로 이동할 수 있다. 즉 N만큼의 반복이 이루어지고 N의 범위는 123,456이다.
• 그럼 용을 쓰러트리기 위한 최소의 생명력(H MaxHP)를 알아내려면 기존 완전탐색대로라면 1부터 시작해서 만족하는 값을 만날때 break하겠지만, 용사의 공격력과 몬스터의 공격력 범위 모두 1,000,000 이다.
• 시간초과가 발생할 수 밖에 없다. 이 때 매우 큰 범위에서 탐색의 시간 복잡도를 O(logN)으로 줄여주는 이분탐색을 사용한다.

 

✍🏻 막힌, 헷갈린 부분

 

이분탐색의 하한선을 어떻게 잡을까?

방향을 틀거나 이동하는 경우가 총 50가지이므로, 넉넉하게 배열의 크기를 100 이상으로 잡고, 중간 지점을 시작점으로 하자

 

❌ 시간초과 발생 풀이

n, p = map(int, input().split())  # 방의 개수, 초기 공격력
arr = []
for _ in range(n):
  t, a, h = map(int, input().split())
  arr.append((t, a, h))
  # t가 1이면 공격력 a, 생명력 h인 몬스터
  # t가 2이면 공격력 a, 생명력 h증가 포션

def can_clear(atk, maxhp):
  current_hp = maxhp
  
  for t, a, h in arr:
    if t == 2:
      atk += a
      current_hp += h
      current_hp = min(current_hp, maxhp)   # 용사 생명력이 maxhp를 넣으면 maxhp
    else:
      monster_a, monster_h = a, h
      while monster_h > 0:  # 몬스터를 쓰러뜨릴때까지 반복
        monster_h -= atk
        if monster_h <= 0:
          break
          
        current_hp -= monster_a
  
        if current_hp <= 0:
          return False
  
  return True

start, end = 1, n*int(1e12)
answer = 0

while start <= end:
  mid = (start + end) // 2

  if can_clear(p, mid):
    answer = mid
    end = mid - 1   # 범위를 더 낮춰보기
  else:
    start = mid + 1

print(answer)

 

- 이분탐색을 통해 범위를 줄여나가며, mid값이 문제 조건에 따라 움직였을 때 마지막 방에 있는 몬스터까지 죽일 수 있는지를 판단한다.

- start는 1로 하고, end는 n * int(1e6) * int(1e6)인 n * int(1e12)로 설정한다. (꼭 이 값 아니어도 범위 내 값을 구할 수 있을정도로 큰 값이면 무관함)

 

* 하한선이 n * int(1e6) * int(1e6) ?

모든 방(n)이 포션이 없는 몬스터가 있는 방이고, 몬스터의 공격력이 1e6, 체력이 1e6, 용사의 공격력이 1이라고 가정했을 때의 최악의 수로 가정

 

-  그런데 문제 조건대로 몬스터의 생명력이 0 이하가 될때까지 (전투가 종료될 때까지) 용사가 공격하는 부분인 while 문을 이유로 시간초과가 발생한다.

 

✅ 통과 풀이

import math

n, p = map(int, input().split())  # 방의 개수, 초기 공격력
arr = []
for _ in range(n):
  t, a, h = map(int, input().split())
  arr.append((t, a, h))
  # t가 1이면 공격력 a, 생명력 h인 몬스터
  # t가 2이면 공격력 a, 생명력 h증가 포션

def can_clear(atk, maxhp):    # atk: 용사의 공격력, maxhp: 후보가 될 수 있는 용사의 생명력
  current_hp = maxhp
  
  for t, a, h in arr:    # a: 공격력, h: 생명력
    if t == 2:
      atk += a
      current_hp += h
      current_hp = min(current_hp, maxhp)   # 용사 생명력이 최대 생명력(maxhp)를 넘으면 maxhp
    else:
      current_hp -= (math.ceil(h/atk)-1) * a
 
      if current_hp <= 0:
        return False
  
  return True

start, end = 1, n*int(1e12)
answer = 0

while start <= end:
  mid = (start + end) // 2

  if can_clear(p, mid):
    answer = mid
    end = mid - 1   # 범위를 더 낮춰보기
  else:
    start = mid + 1

print(answer)

 

- t가 1일때, 즉 몬스터가 있는 방에 들어가서 몬스터를 공격하는 부분에서의 코드를 수정했다.

      current_hp -= (math.ceil(h/atk)-1) * a
 
      if current_hp <= 0:
        return False

 

- ceil(h / atk): h인 몬스터를 생명력을 0이하로 떨어뜨려 쓰러뜨리게 하기 위한 공격력이 atk인 용사가 공격하는 횟수이다.

- ceil을 하는 이유는 예를들어 h가 10이고, atk가 4라고 해보자. 용사가 몬스터를 무찌르기 위해서 h // atk = 2가 아닌 3회일 것이다. (4 + 4 했는데 아직 몬스터의 생명력이 2가 남아있으니 한번 더 공격해야함). 따라서 소수점이 남아있는 수를 올림해준다.

- 최종적으로 -1 을 하는 이유는 몬스터를 죽인 마지막의 경우, 용사는 공격을 받지 않기때문에 -1을 해준다.
즉 math.ceil(h/atk) - 1은 용사가 몬스터에게 공격받은 총 횟수이다.

- 따라서 용사의 각 경우마다의 체력은(current_hp) = 몬스터에게 공격받은 횟수 * 몬스터의 공격력
이를 식으로 세우면 current_hp = (math.ceil(h/atk) - 1) * a가 된다.