먼저 문제가 심플해서 아주 맘에 듭니다 ^ ^;;

문제를 충분히 읽어보았다면, 다음과 같은 결론을 내릴 수 있어야 합니다.

• 무적권은 지나온 라운드에서 가장 많은 적이 나왔던 라운드에서 사용해야 매우 효과적이다.

• 무적권을 사용하면, 병사의 수가 차감되지 않는다.

뭐 아주 당연한 말을 하냐고 싶을 겁니다.

네 맞습니다. 아주 당연한 문제입니다.

라운드를 돌파하면서, 적과 마주 싸우고, n에서 enemy[i] 만큼 감소하면 됩니다.

그리고, n이 0 미만이 된다면, 무적권을 사용하면 됩니다.

여기서 핵심이 있습니다.

문제에서는 무적권을 해당 라운드에서만 사용해야 할 것처럼 속이고 있습니다.

물론 게임 규칙에서는 해당 라운드에서만 무적권을 사용해야합니다.

하지만, 우리는 결론만 구하면 되기에, 지나온 라운드에도 무적권을 사용해도 상관없습니다.

어차피 개이득 본 병사 수만 추가적으로 n에 더해주기만 하면 되니까요.

사실 여기까지 눈치채셨다면, 문제는 금방 풀 수 있습니다.

지나온 라운드 중에서 가장 적의 수가 많았던 라운드에 무적권을 사용하면 되기 때문이죠.

그리고 무적권을 사용했으니 그만큼 n에 가산해주면 됩니다.

그럼, 지나온 라운드중에서 가장 적이 많았던 라운드를 어떻게 알아낼까요?

바로 그거에 적합한 기가막힌 자료구조가 하나 떠오르지 않나요?

그렇습니다.

heap구조를 사용하면 됩니다. 그 중에서도 최대힙을 사용하면 됩니다.

최대힙을 간단하게 만들려면, 그냥 숫자를 음수로 바꾸어서 저장하면 됩니다.

그럼, 수가 전체적으로 반전이 되어, 가장 큰 수가 가장 작은 수가 되죠.

heap자료구조는 삽입, 꺼내기 연산이 O(logN)의 속도로 매우 빠른 연산 능력을 보여주는 좋은 자료구조입니다.

이를 통해, n이 부족하여, 무적권을 사용할 때, 과거에 가장 많은 적을 만났던 라운드의 값에 사용하여, n에 그대로 더해주면 됩니다.

생각보다 간단해서 놀랐나요?

저도 놀랐습니다.

감사합니다.