프로그래머스 level2 [디펜스 게임] 파이썬

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

프로그래머스

#프로그래머스 level2 디펜스 게임
import heapq
def solution(n, k, enemy):
    answer = 0
    i=0
    heap=[]
    len_enemy=len(enemy)
    while True:
        # print(n,enemy[i])
        if i==len_enemy:
            return len_enemy
        if n>=enemy[i]:
            heapq.heappush(heap,-enemy[i])
            n-=enemy[i]
        else:
            if k>0:
                if heap:
                    M=-heapq.heappop(heap)
                    if M<enemy[i]:
                        heapq.heappush(heap,-M)
                        k-=1
                        i+=1
                        continue
                    n+=M
                    k-=1
                    continue
                else:
                    k-=1
                    i+=1
                    continue
            else:
                break
        i+=1
    return i

처음에는 재귀를 통해서 문제를 해결하려고 하였으나, 당연하게도 시간초과가 발생하였다.
코드를 변경해 그리디로 해결하였다.

알고리즘은 다음과 같다.
1. n이 현재 적(enemy[i])보다 크거나 같으면 현재 적을 처리한다. (n=n-enemy[i])
2. n보다 현재 적이 더 크면
2-1) k가 0보다 큰 경우: 처음 적~ 현재 적까지중 가장 많은 수의 적이 있는 라운드에 무적권을 사용한다.
2-2) 없으면 현재 라운드를 반환한다.
3) 모든 라운드에서 생존하면 그 길이를 반환한다.