[Programmers] Level 2. 디펜스 게임

🔗 Problem Link

프로그래머스

---

❔Thinking

• enemy에 담긴 적들을 라운드마다 차례대로 제거할때, 가장 많은 라운드 버틸 방법을 생각한다.
• '무적권'은 k개 만큼 쓸 수 있고, 쓰는 라운드에 따라 결과가 달라질 수 있다.
• n=10, k=1일 경우, [10,3,7]을 1라운드만에 끝나거나 3라운드 모두를 버틸 수 있다.

---

💻Solution

import heapq

def solution(n: int, k: int, enemy: list) -> int:
    max_heap = []  # 지금까지 만난 적을 저장할 최대 힙

    for round_num, e in enumerate(enemy):
        n -= e  # 현재 적을 체력으로 처리
        heapq.heappush(max_heap, -e)  # 최대 힙에 현재 적 추가
        
        if n < 0:  # 체력이 부족한 경우
            if k > 0:  # 무적권을 사용할 수 있으면
                n -= heapq.heappop(max_heap)  # 가장 큰 적을 무적권으로 대체
                k -= 1
            else:  # 무적권도 없으면 종료
                return round_num

    return len(enemy)  # 모든 라운드를 성공적으로 처리

---

🗝️keypoint

1. 무적권은 가장 큰 적에게 사용할수록 이득이기 때문에, n이 0이하일때 무적권을 쓸 수 있는 적들을 생각한다.
2. brute force 방법으로는 더 효율적인 대결을 확인할 수 없다. (ex - [10,3,7])