[프로그래머스 - Python] 142085 - 디펜스 게임

0.  문제 링크

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/142085

프로그래머스

---

1.  풀이 방법

 

 

1. 일단 문제를 보면 최소 비용으로 막아야 되는 게 확실하고, K개는 무손실로 막을 수 있다.
2. 따라서 적군이 들어올때마다 힙에다가 집어넣는다. 
3. 만약 힙의 크기가 K를 넘는다면, 가장 작은 적군의 수를 빼서 나의 병사에서 뺀다.
4. 결론적으로 가장 작은 적군만 선택해서 막은 상태가 된다.

---

2.  코드

 

 

import heapq

def solution(n, k, enemy):
    answer = 0
    
    l = len(enemy)
    if k >= l:      # 모두 다 막을 수 있음
        return l
    
    hp = list()
    for i in range(k):      # k개까지는 일단 때려박음
        heapq.heappush(hp, enemy[i])
    
    while n >= 0 and (i := i + 1) < l:      # n이 0보다 크거나 같고, i에는 1을 계속 더함
        heapq.heappush(hp, enemy[i])        # 일단 새로 오는 적을 넣음
        n -= heapq.heappop(hp)      # k의 한도 내에서 가장 작은 애를 뺌. 그러면 hp 안에는 i 라운드까지 중에 가장 큰 적들이 들어가있음

    return i

---

3.  마무리