디펜스 게임

디펜스 게임

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

문제

풀이

처음엔 DFS, BFS 완전탐색을 하였다. 하지만 문제에서 보다시피 n, k, enemy길이가 상당히 큰 것을 알 수 있다. 결국 TLE가 발생하였다.
이 문제에 키는 롤백이다.
n = 7, k = 3, enemy = [4, 2, 4, 5, 3, 3, 1]인 것을 예로 들자면
1라운드에선 enemy = 4이므로 n = 3이 남는다. 그리고 enemy를 우선순위 큐에 넣는다. => q = [4]
2라운드에선 enemy = 2이므로 n = 1이 남는다. 해당 enmey를 우선순위 큐에 넣는다. => q = [4, 2]
3라운드에선 enemy = 4이므로 n이 음수가 된다. 이 때 무조건 무적권을 써야 하는데 우선순위 큐에 담겨있는 q =[4, 4, 2]중 가장 큰 값에 써야 한다. 즉 4에 쓰고 4를 돌려받는다. n = 1, q => [4, 2]가 된다.
4 라운드에선 enemy = 5이므로 n이 음수가 된다. 마찬가지로 무적권을 써야하는데 우선순위 큐에 담겨있는 q = [5, 4, 2]중 가장 큰 값에 쓴다. 5에 쓰고 5를 돌려받는다. n = 1, q => [4, 2]가 된다.
5 라운드에선 enemy = 3이므로 n이 음수가 된다. 마찬가지로 무적권을 써야하는데 우선순위 큐에 담겨있는 q = [4, 3, 2]중 가장 큰 값 4에 쓴다. 4를 돌려받는다.
n = 2, q => [3, 2]가 된다.
6 라운드에선 enemy = 3이므로 n이 음수가 된다. 하지만 k를 다 소모했으므로 5를 리턴한다.

이것을 코드로 나타내면 다음과 같다.

from heapq import heappush, heappop
def solution(n, k, enemy):   
    q = []
    total = 0
    answer = 0
    for each in enemy:
        heappush(q, -each) ## 우선순위 큐에 넣기
        total += each      ## enemy 총합 계산
        
        if total > n:      ## enemy총합이 n보다 크면 무적권 써야함
            if k > 0:      ## 무적권이 남아 있다면
                total -= -heappop(q)    ## 우선순위 큐에 저장된 최대값을 롤백
                k -= 1                  ## 무적권 개수 차감
            else:          ## 무적권이 없다면 종료
                break
        answer += 1       
    return answer
        

결과

파이썬에서 heapq는 최소값으로 되어 있다. 그래서 최대값을 구하기 위해선 음수를 heappush해주고 heappop할 때 음수를 곱해주면 최대값을 구할 수 있게 된다.

조건이 너무 크면 완전탐색말고 그리디한 방법으로 생각하는 연습을 해야한다.