프로그래머스_level2_디펜스 게임 (python)

★ 접근

모든 경우의 수를 살펴봐야하고, 엄청난 크기의 병사, 최대 백만인 라운드 수 이 요소들을 종합적으로 미루어 봤을 때 그리디 알고리즘을 떠올릴 수 있다. 근데 여기서 그리디만을 가지고는 풀 수 없다. 그리디인데도 불구하고 시간초과가 날 것이다. 우선순위 큐 알고리즘도 접목시켜야 풀 수 있다.

 

★ 풀이

 매번 라운드 적군과 맞서 싸운다. 그러다가 아군 병사의 숫자가 적군의 병사의 숫자보다 부족할 경우 무적권을 써야한다.

이 때 무적권이 한 장도 남지 않았다면 게임을 종료시킨다. 

무적권이 남아있다면 음수가 돼도 괜찮으니 현재 남은 아군 병사에 현 라운드 적군 병사의 숫자만큼 뺀다. 그리고 현재 적군 숫자를 우선순위 큐에 넣은다음 이제까지 치뤘던 전투 중 가장 적군이 많았던 숫자를 꺼낸 다음 현재 병사에 더해준다.

 

★ 코드

import heapq
def solution(n, k, enemys):
    answer = 0
    q = []
    for enemy in enemys:
        if n >= enemy:
            n -= enemy
            heapq.heappush(q, -enemy)
        else:
            if k < 1:
                break
            else:
                n -= enemy
                k -= 1
                heapq.heappush(q, -enemy)
                num = -heapq.heappop(q)
                n += num
        answer += 1
    return answer

 

★ 회고

 처음에 그리디 문제인 것을 바로 떠올렸지만 시간초고가 나지 않게 어떻게 할 것인지 떠올리기 힘들었다. 문제를 풀다가 든 생각이지만 만약 게임을 클리어할 수 있다고 했을 때 병사의 수를 최대한 많이 남겨야 한다는 조건이 붙었을 때 어떻게 풀어야지 생각을 해봤는데 위 풀이랑 로직이 똑같을 것이다. 위 로직도 최대한 적군이 많았을 때 무적권을 사용하기 때문이다.