문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/142085
문제 설명
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
- 준호는 처음에 병사 n명을 가지고 있습니다.
- 매 라운드마다 enemy[i]마리의 적이 등장합니다.
- 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
- 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
- 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
- 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
- 무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.
문제 해설 및 코드 설명
일단 문제에서 중요하게 볼 필요가 있는 부분은 누가 뭐래도 무적권인 것 같다. 이 무적권을 가장 효율적으로 사용할 방법을 모색해야 하는데, 필자의 접근법은 무적권을 그냥 되살리기로 보자는 것이다. 이전에 소모한 병사의 수 중에 가장 큰 경우를 찾아서 되살리면 된다.
필자는 매턴 삽입 및 정렬이 필요하기 때문에 heap을 사용했다. 일단 for문을 이용해 병사의 소모전을 진행하고 소모한 병사의 수(적의 수)를 heap에 넣었다. 그리고 병사의 수가 0보다 작은 경우, 병사를 살려내도록 로직을 구성했다. 이렇게 되면 방금 전에 전멸한 경우에도 되살려낼 수 있으므로 모든 경우에서 참이 성립한다.
import heapq
def solution(n, k, enemy):
max_heap = []
for stage in range(len(enemy)):
n = n - enemy[stage]
heapq.heappush(max_heap, -enemy[stage])
if n < 0:
if k > 0:
n += -heapq.heappop(max_heap)
k -= 1
else:
return stage
return len(enemy)
continuous programming