[코딩 인터뷰][HackerRank] Mandragora Forest

※ 이 포스트는 HackerRank 문제인 Mandragora Forest 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

---

Mandragora Forest

문제 출처 : https://www.hackerrank.com/challenges/mandragora/problem
카테고리 : Greedy
난이도 : Medium (50 point)

---

문제 설명

용사가 모험을 떠난다. 용사의 스탯은 체력포인트 s와 경험치 p가 있다. 어떤 몬스터를 마주쳤을 때, 용사는 몬스터를 해치우거나 먹어치울 수 있다. 몬스터를 먹어치우면 체력포인트 s가 1증가한다. 몬스터를 해치울 경우엔 몬스터가 주는 경험치 H에 자신의 체력 s를 곱한만큼 경험치를 얻는다.

각 몬스터가 주는 경험치가 배열 H로 주어진다. 예를 들어 [2, 3, 5]는 몬스터 3마리가 각각 2, 3, 5의 경험치를 준다는 말이다. 용사가 어떤 몬스터를 먼저 상대할지 임의로 선택할 수 있다고 할 때 얻을 수 있는 경험치의 최댓값을 구하여라.

예를 들어 위 경우에서는 경험치 2짜리는 먹고, 나머지는 해치워서 총 경험치 2 x (3 + 5) = 8를 얻을 수 있다.

---

문제 풀이

만약 어떤 몬스터를 해치울 것이라고 결정했다고 생각하자. 몬스터를 해치울 당시의 체력 s는 클수록 좋으니 가능한 마지막에 해치우는게 좋다. 즉, 해치우는 행동은 먹는 행동보다 뒤에 오는게 무조건 좋다는 말이다.

그렇다면 무엇을 해치우고, 무엇을 먹을 것인가? 경험치가 작은 순서로 먹어치우는게 당연히 좋다. 경험치가 적은놈이건 큰 놈이건 체력은 1만 오르니까. 따라서 일단 경험치 순으로 몬스터를 정렬시킨후에, 어디까지 먹어치우는게 좋을지 결정하면 된다.

어디에서 멈출지 결정하는 것은 간단하다. 어떤 몬스터를 먹는다면 그 몬스터를 해치움으로써 얻는 경험치 s x H[i]를 잃게 된다. 대신에 그 다음 몬스터들에 대해서 s가 1증가한만큼 경험치를 먹을 수 있으므로 sum(H[i + 1], … , H[N – 1])만큼의 경험치를 얻게된다. 이 차이를 계산해서 이득일 때까지 계속 진행한다.

만약 손실이거나 비기는 지점을 만난다면 거기에서 탐색을 종료하면 된다. 그 다음 비교에서는 s x H[i + 1]과 sum(H[i + 1], … , H[N – 1])을 비교할 건데 좌변은 커졌고, 우변은 작아졌기 때문에 그 비교결과도 당연히 손실이거나 비김이기 때문이다. 즉, 처음으로 손실이거나 비기는 지점부터는 무조건 해치워서 경험치를 얻는 방식으로 진행하면 된다.

---

코드

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the mandragora function below.
def mandragora(H):
    H.sort()
    N = 1
    Sum = sum(H)
    for i in range(len(H)):
        Sum -= H[i]
        if N * H[i] < Sum:
            N += 1
        else:
            return (Sum + H[i]) * N


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        n = int(input())

        H = list(map(int, input().rstrip().split()))

        result = mandragora(H)

        fptr.write(str(result) + '\n')

    fptr.close()

---

코딩 인터뷰 – Mandragora Forest