이 문제는 '무적권'을 어느 조건에 써야 할지 결정하는 것이 중요하다. 준호가 디펜스 게임을 하는 당시에는 미래를 예측할 수 없기에, 적들을 많은 순서대로 미리 정렬하고 게임을 진행하고자 한다.
처음에는 파이썬 람다식을 사용하여 적이 많은 순서(내림차순), 인덱스가 작은순서(오름차순)로 정렬 후 정렬된 배열의 k번째까지의 인덱스들에 해당하는 값을 enemy 배열에서 0으로 초기화하는 작업을 하였다. 이는 당연히 틀린 접근이다. 왜냐하면, 0으로 초기화하지 않은 지점에서 준호의 병사 n이 모자랄 수도 있기 때문이다.
따라서 enemy를 미리 정렬하고 적용하는 것은 풀이에 도움이 되지 않는다. 결국 구글링을 통해 맞는 풀이를 찾게 되었고, 대부분의 풀이는 '소급 적용'의 개념을 활용(내가 생각한 나만의 개념이다:). 이 비유가 독자로 하여금 이해하는데에 도움이 되었으면 한다.)하여 풀이한 것을 확인할 수 있었다. 해당 풀이에 대해 이해한 과정과 고민한 흔적을 남겨보자고 한다.
소급적용
직역하자면 "거슬러 올라감". 쉽게 말해 새로이 도입된 어떤 제도나 법(法) 등이 과거에 있었던 사건에도 영향을 끼치게 되는 경우를 말한다. 예를 들어 2021년에 새로이 제정된 법률에 근거해 2019년에 일어난 사건을 해결했다면 2021년의 법률이 2019년에 소급되었다고 표현할 수 있다.
[출처: 나무위키]
🤔접근
상식적으로
- 적이 많은 라운드에서 '무적권'을 사용하는 것이 많은 라운드를 통과하는데에 도움이 될 것이다.
- 또한, 가지고 있는 '무적권'은 당연히 모두 사용해야 한다.
이 문제를 '테트리스 게임'에 비유해서 생각해보자. 테트리스 게임에서 테트리스가 차곡차곡 쌓이는 그림을 상상해보자. 기존의 테트리스 게임과 다른 점은 '무적권'이 존재하는 한 한계선(준호가 가지고 있는 병사 n)을 넘을 경우 이전에 쌓았던 블럭(전사한 준호의 병사들)을 '무적권'을 사용하여 뺄 수 있다는 것이다. 즉, 전사한 준호의 병사들을 소생시키는 셈이다. 이러한 과정을 '무적권'을 모두 사용할 때까지 반복한다. 단, 한계선을 넘지 않는다면 계속 블럭을 쌓는다(준호의 병사를 희생시킨다).
한편, 위의 조건에 따라 이전에 쌓았던 블럭을 뺄 때는 가장 큰 블럭을 빼게 된다. 이를 위해서는 이전에 쌓았던 모든 블럭들의 크기를 기억하고 있어야 한다. 따라서 이를 구현하기에 가장 효율적인 방법인 '큐'를 활용한다. 또한, 한계선을 넘을시, '무적권'이 있는 경우는 무적권 사용한다.
✏️ 풀이
import heapq as hq
def solution(n, k, enemy):
if k >= len(enemy):
return len(enemy)
answer = 0
num = 0
heap = []
for e in enemy:
hq.heappush(heap, -e)
num += e
if num > n:
if not k:
break
k -= 1
num += hq.heappop(heap)
answer += 1
return answer