[파이썬] 디펜스 게임

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  • 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

---

입출력 예nkenemyresult

7	3	[4, 2, 4, 5, 3, 3, 1]	5
2	4	[3, 3, 3, 3]	4

---

입출력 예 설명

입출력 예#1

• 1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.

입출력 예#2

• 준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.

 

 

🌱 나의 풀이

import heapq
def solution(n, k, enemy):
    answer = 0
    heap = []
    total = 0
    for i in enemy :
        heapq.heappush(heap, -i)
        total += i
        if total > n :
            if k == 0 :
                break
            k -= 1
            total += heapq.heappop(heap)
        answer += 1
    return answer

최대 힙 사용

무적권은 힙에 넣어두고 가장 적이 많은 순서대로 뽑아서 쓴다. ➡️ total에서 차감

total은 n을 사용한 합계

 

 

# 실패
def solution(n, k, enemy):
    answer = 0
    for i in enemy :
        if n < i and k == 0 :
            break
        if n < i :
            k -= 1
            answer += 1
            continue
        n -= i
        answer += 1
    return answer

아래보다 정답율이 높아졌지만, 부족하다.

범위 안에서 가장 높은 적이 들어있는 순서대로 무적권을 쓰고 난후 나머지의 합이 n이하가 되야 모든 라운드 통과하게 할까?

 

# 실패
import bisect

def solution(n, k, enemy):
    answer = 0
    size = len(enemy) + 1
    arr = [0] * size
    for i in range(1, size) :
        arr[i] = arr[i-1] + enemy[i-1]
    idx = bisect.bisect_left(arr, n) - 1
    answer = idx + k
    n -= arr[idx]
    if idx + k < size -1 :
        if enemy[idx + k] <= n :
            answer += 1
    return answer

아래 코드에서 보완했다.

무적권을 다쓴 후 n으로 할 수 있는지

만약에 무적권을 안 써도 되는 곳에 쓰는 경우가 있을 수 있다.

차례대로 n을 다 소진하는 것은 좋은 방법이 아니다.

 

# 실패
import bisect

def solution(n, k, enemy):
    size = len(enemy) + 1
    arr = [0] * size
    for i in range(1, size) :
        arr[i] = arr[i-1] + enemy[i-1]
    return bisect.bisect_left(arr, n) + k - 1

arr은 누적합 리스트다.

일단 n을 쓸수 있을 때까지 쓰고 난후 무적권을 사용했다.

무적권을 사용한 후에 남은 n을 사용할 수 있는지 확인해야 한다.

만약에 n=5, k=2, enemy=[2, 1, 3, 3, 2]라면 답은 5다.

내가 짠 코드는 4가 나온다.

 

 

⭐ 다른 사람 풀이

import heapq as hq

def solution(n, k, enemy):
    q = enemy[:k]
    hq.heapify(q)
    for idx in range(k, len(enemy)) :
        n -= hq.heappushpop(q, enemy[idx])
        if n < 0 :
            return idx
    return len(enemy)

heappushpop을 이용해서 push와 pop을 동시에 한다.

 

 

 

문제 출처 👉 프로그래머스