(백준 16434 드래곤 앤 던전

• tags : (algorithm

  No matching post could be found

  - (binary search - (simulate
• 문제 링크 : https://www.acmicpc.net/problem/16434
• 풀이 링크
  • Python

• 조금 독특한 매개변수 탐색 문제인데, 매개변수 탐색 과정을 활용하면 단순한 구현 방식으로 해결할 수 있다.
• 매개변수 탐색에서 최댓값 설정을 하며 몇 차례 틀렸는데, 최댓값 부분은 아직 잘 이해가지 않는다.

def bin_search(H: int, dungeons: list[tuple[int]]) -> int:
    left, right = 0, 10**17
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if simulate(mid, H, dungeons):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return 

• right를 10^17으로 설정했을 때 통과했다.
  • 10^12 부터 10^16까지 순차적으로 계산해보았고, 10^17에서야 통과했다.
  • 정확한 계산은 잘 모르겠지만, 생각보다 큰 수로 설정해야 했다.

def simulate(health: int, attack: int, dungeons: list[tuple[int]]) -> bool:
    max_health = health
    for t, a, h in dungeons:
        if t == 1:
            turn = h // attack if h % attack == 0 else h // attack + 1
            if health - a * (turn - 1) <= 0:
                break
            health -= a * (turn - 1)
        else:
            attack += a
            health = min(health + h, max_health)
    else:
        return True
    return False

• 가능한지 확인하기 위해, 체력을 기준으로 모든 턴을 실행하며 확인했다.

HP = 0
answer = 0
for _ in range(N):
    t, a, h = MIIS()
    if t == 1:
        turn = h // H if h % H == 0 else h // H + 1
        HP += a * (turn - 1)
        answer = max(answer, HP)
    else:
        H += a
        HP = max(HP - h, 0)
print(answer + 1)

• 바로 위의 simulate()함수를 확장하여, 필요한 체력을 역으로 계산하였고, 더욱 빠르고 편하게 정답을 구할 수 있다.