BOJ :: [16434] 드래곤 앤 던전

문제

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

16434번: 드래곤 앤 던전

---

문제 요약

드래곤 앤 던전 문제는 용사가 N개의 모든 방을 방문하여 마지막 N번째 방 있는 공주를 구하려고 할 때 필요한 용사의 최대 생명력을 구하는 문제이다. 방은 2종류로 구성되어 있으며 1번방은 공격력이 a, 체력이 mh인 몬스터가 있고 2번 방에는 용사의 공격력을 at만큼 증가시키고 체력을 h만큼 회복하는 포션이 들어있는 방이다.

 

1번 방에 들어가는 경우 다음과 같이 전투가 진행된다.

1. 용사의 공격력 at만큼 몬스터의 생명력을 깎습니다.
2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
3. 몬스터의 공격력만큼 용사의 생명력 hp를 깎습니다.
4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
5. 다시 1부터 진행합니다.

2번방에 들어가는 경우 용사의 체력을 h만큼 증가시키고, 공격력을 at만큼 증가시킨다.

 

우리는 용사가 N개의 방을 모두 방문하여 성공적으로 공주를 구출하기 위해 필요한 최대 생명력(H_max)을 구해야 한다.

풀이

이 문제는 이분 탐색과 그리디 2가지 방법으로 문제를 해결할 수 있다.

 

[그리디]

용사가 1번방에 들어갈 경우 (몬스터의 체력 / 용사의 공격력) * 몬스터의 공격력만큼 체력이 감소한다.

용사가 2번방에 들어갈 경우 현재 용사의 체력은 포션의 체력만큼 더해지고 공격력도 포션의 공격력만큼 더해진다.

우리는 용사의 최대 체력을 구하면 되기 때문에 1번방에 들어가 몬스터에게 공격받는 만큼의 체력을 더해주고, 2번 방에 들어가 포션을 먹는 만큼 체력을 감소시키면서 모든 방을 탐색하여 용사에게 필요한 최대 체력을 구할 수 있다.

 

구현하면서 유의해야할 점은 용사의 체력이 0인 경우 게임이 종료되기 때문에 용사의 체력은 1로 시작하고, 포션으로 체력을 감소시키는 경우 체력이 1보다 작아지면 용사의 체력을 1로 초기화해야 한다.

 

그리디 하게 문제를 푸는 경우 N번만에 해결할 수 있기 때문에 시간 복잡도가 선형으로 빠르게 풀이할 수 있다.

 

<코드 - 그리디>

import sys
input = sys.stdin.readline

N, sp = map(int, input().split())

hp = 1
arr = []

for i in range(N):
    tmp = list(map(int, input().split()))
    arr.append(tmp)
    
maxHP = 0

for i in range(N):
    if arr[i][0] == 1:
        tmp = arr[i][2] // sp
        tmp *= arr[i][1]

        flag = arr[i][2] % sp
        
        if flag == 0:
            tmp -= arr[i][1]
            
        hp += tmp
    else:
        sp += arr[i][1]
        hp -= arr[i][2]

        if hp < 1:
            hp = 1
            
    if maxHP < hp:
            maxHP = hp

print(maxHP)

 

그리디 방법 채점 결과

---

[이분탐색]

이 문제를 이분 탐색으로도 풀이할 수 있다.

 

오른쪽을 가리키는 포인터 right를 최댓값으로 두고 이분 탐색을 사용하여 용사의 체력을 구할 수 있다.

중간값을 용사의 최대 체력으로 가정하고 N개의 방을 모두 방문하게 한다. N개의 방을 모두 방문하면서 용사의 체력이 1 미만인 경우 현재 중간값으로는 N개의 방을 모두 방문할 수 없다. 따라서 N개의 방을 모두 방문할 수 없는 경우 left를 mid + 1로 설정하여 용사의 체력을 늘려주고, 현재 중간값으로 N개의 방을 방문이 가능하면 right를 mid - 1 값으로 설정하여 체력을 줄여나가며 용사에게 필요한 최대 체력을 구할 수 있다.

 

<코드 - 이분 탐색>

import sys
input = sys.stdin.readline

def binary(hp):
    global N
    
    thp = hp
    at = attack

    for i in range(N):
        if rooms[i][0] == 1:
            tmp = (rooms[i][2] // at) * rooms[i][1]

            #만약 나누어 떨어진다면 한대 덜 맞기 때문에 공격력 만큼 감소
            if rooms[i][2] % at == 0:
                tmp -= rooms[i][1]

            thp -= tmp
        else:
            at += rooms[i][1]
            #용사에게 필요한 maxHP를 구하지만 최소 maxHP를 구해야 하기 때문에 현재 hp와 mid값 중 작은 값을 선택
            thp = min(thp + rooms[i][2], hp)

        if thp < 1:
            return False

    return True

N, attack = map(int, input().split())

rooms = []

for i in range(N):
    rooms.append(list(map(int, input().split())))

right = 999999000001 * N
left = 1

while left <= right:
    mid = (left + right) // 2
    if binary(mid):
        right = mid - 1
    else:
        left = mid + 1

print(left)

 

이분탐색 방법 채점 결과

이분 탐색으로 풀이하는 경우 시간 복잡도가 O(n * log n)으로 그리디 하게 풀이하는 방법보다 시간이 오래 걸린다.

 

 

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다 . 질문도 환영합니다! :)