[Programmers] 디펜스 게임 바로가기
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n
명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
n
명을 가지고 있습니다.enemy[i]
마리의 적이 등장합니다.enemy[i]
명 만큼 소모하여 enemy[i]
마리의 적을 막을 수 있습니다.무적권
이라는 스킬이 있으며, 무적권
을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.무적권
은 최대 k
번 사용할 수 있습니다.준호는 무적권
을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 n
, 사용 가능한 무적권의 횟수 k
, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy
가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.
n
≤ 1,000,000,000k
≤ 500,000enemy
의 길이 ≤ 1,000,000enemy[i]
≤ 1,000,000enemy[i]
에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.enemy[i]
의 길이를 return 해주세요.n | k | enemy | result |
---|---|---|---|
7 | 3 | [4, 2, 4, 5, 3, 3, 1] | 5 |
2 | 4 | [3, 3, 3, 3] | 4 |
입출력 예 #1
입출력 예 #2
heap
) 자료구조이다.for e in enemy:
heappush(heap, -e)
sumEnemy += e
if sumEnemy > n:
if k == 0:
break
sumEnemy += heappop(heap)
k -= 1
answer += 1
e
)를 최대힙 자료구조(heap
)에 음수형식으로 저장한다.sumEnemy
)에 적의 수(e
)를 누적으로 더한다.sumEnemy
)가 보유한 병사(n
)보다 많을 경우k
)도 존재하지 않는다면 더 이상 라운드를 진행할 수 없다(break
).heap
)에서 지금까지 진행해온 라운드 중 적이 가장 많은 라운드를 찾아서(heappop
) 적의 전체 수(sumEnemy
)의 값을 차감하고, 무적권(k
)의 수도 1
만큼 차감한다.from heapq import heappop, heappush
def solution(n, k, enemy):
answer, sumEnemy = 0, 0
heap = []
for e in enemy:
heappush(heap, -e)
sumEnemy += e
if sumEnemy > n:
if k == 0: break
sumEnemy += heappop(heap)
k -= 1
answer += 1
return answer