프로그래머스 디펜스 게임 python

📘 프로그래머스 디펜스 게임 python

---

✅ 문제 요약

• n명 병사로 적의 공격을 순서대로 막아야 함
• 매 라운드마다 적 enemy[i]명이 등장함
• 병사로 막으면 n -= enemy[i]
• 병사가 부족하면 무적권을 써서 병사 소모 없이 막을 수 있음
• 무적권은 k번만 사용 가능
• 게임오버 조건: 병사도 없고, 무적권도 없고, 막아야 할 적이 있음

---

🎯 목표

무적권을 적절히 사용해서 가능한 많은 라운드를 버텨야 한다.

---

🔍 핵심 아이디어 요약

"병사가 모자라는 순간, 지금까지 막았던 적 중 가장 큰 enemy[i]에 무적권을 소급 적용해 게임오버를 피한다."

---

🧠 왜 이 방식이 정답을 보장하는가?

💡 병사는 계속 줄어들지만, 무적권은 유한하므로 아껴 써야 함

• 병사는 매 라운드 enemy[i]만큼 줄어듭니다.
• 무적권은 정해진 횟수(k)만 사용할 수 있습니다.
• 따라서 무적권은 가장 효과가 클 때 사용해야 합니다.

💡 무적권은 "소급 적용"해야 이득

• 예를 들어 병사가 n = 10, 무적권 k = 1, 적 리스트가 [4, 3, 6]이라고 하면:

라운드	적 수	병사 남은 수	설명
1	4	6	병사 사용
2	3	3	병사 사용
3	6	-3	병사 부족!

• 이때 무적권이 하나 있다면? → 1, 2, 3 중 가장 적 수가 많은 3라운드가 아니라 → 지금까지 막은 라운드 중 가장 큰 수(=6)를 무적권으로 되돌려야 한다.
• 즉, 3라운드를 병사로 막고 n < 0이 되면, → 무적권 1개를 써서 **가장 많은 병사가 소모된 라운드(6)**를 **무적권으로 치환** → 그 병사 수만큼 n을 복구할 수 있다.

---

💾 heapq를 사용하는 이유

• 지금까지 막은 적들 중 enemy[i]가 가장 큰 값을 빨리 찾아야 함.
• heapq는 Python의 **우선순위 큐(min-heap)**로 가장 작은 값이 먼저 나옴 → 음수를 넣어서 **최대 힙처럼 사용**할 수 있음.

---

🔎 코드 설명

import heapq
def solution(n, k, enemy):
    answer = 0
    N = len(enemy)
    heap = []
    for i in range(N):
        n -= enemy[i]
        heapq.heappush(heap, -enemy[i])
        if n < 0:
            if k > 0:
                n -= heapq.heappop(heap)
                k -= 1
            else:
                return i
    return N

---

📌 핵심 로직 요약

순서	설명
1	모든 라운드에서 기본적으로 병사로 적을 막는다 (n -= enemy[i])
2	매번 막은 적 수를 heap에 저장한다 (음수로 최대 힙처럼)
3	병사가 부족해지면 (n < 0) → 게임오버 직전
4	이때 가장 많은 병사가 필요했던 라운드를 무적권으로 치환 (heappop())
5	병사 수를 복구하고 무적권 사용 횟수를 줄인다
6	무적권이 다 떨어졌고 병사도 없으면 즉시 종료한다

---

✅ 왜 이 방법이 최적인가?

• 탐욕(Greedy) 전략: 가장 큰 비용을 줄이는 것이 전체 이득을 극대화
• 게임오버 전 소급 적용: 병사가 모자란 시점에서 가장 효과적인 되돌리기
• heapq 사용: 가장 큰 enemy[i]를 O(log n) 시간에 찾아낼 수 있음

---

📈 시간 복잡도

• enemy 리스트 길이 = N
• 매 반복마다 heapq.heappush + 조건 시 heappop 1회
• 모두 O(log N)이므로 전체는 O(N log N)
• 문제 조건 (최대 길이 1,000,000) 충분히 통과 가능

---

📌 결론 요약

무적권은 병사 소모를 줄이기 위해 쓰는 것이 아니라, 게임오버 직전 병사 수 부족을 피하기 위해, 과거의 가장 큰 적에 소급 적용해야 한다. 이 전략을 heap을 통해 효율적으로 구현하면 가장 많은 라운드를 막을 수 있으며, 해당 코드는 이 논리를 정확히 구현하고 있어 정답을 보장한다.