[ 프로그래머스 / LV2 ] 디펜스 게임 (파이썬 Python )

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

프로그래머스

 

코드

---

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

 

풀이

---

처음에는 순차적으로 탐색하며 어떤 값에 무적권을 사용할 지 선정하기가 너무 까다로웠다.

조건이 너무 많았고 이를 정할 수 없다고 생각해서 완전탐색으로 해결하려 했다. 완전탐색은 당연하게도 시간초과가 발생했다.

 

그 후 질문하기에서 아이디어를 얻었고 그 아이디어는 다음과 같다.

" 막히는 라운드가 생길 때마다 막히는 라운드와 지나온 라운드 중에 가장 큰 값에 무적권을 사용한다"

 

반드시 현재 라운드에서 현재 라운드에 무적권을 사용할 필요는 없었던 것이다.

따라서 지날 수 있는 라운드는 모두 지나면서 우선순위큐에 저장하고 막히는 라운드가 생긴다면 지금까지의 모든 라운드 중 가장 큰 값에 무적권을 사용한다.