[프로그래머스] 디펜스 게임 LV.2

[프로그래머스] 디펜스 게임 LV.2

포인트

무적권을 잘 사용하여 최대한 많은 스테이지를 클리어한다. 즉, 무적권을 어떻게 사용할 것인지를 생각해야 한다.

발상

무적권을 언제 사용해야 하는가?

일반적으로 무적권은 enemy[i]가 큰 경우에 사용하는 것이 이득일 것입니다.

하지만, 이 문제는 스테이지를 순차적으로 클리어하며 진행하는 것이기 때문에 현재 스테이지의 enemy[i]가 이 뒤의 스테이지보다 큰 것인지 작은 것인지는 알 수 없습니다. 즉, 무적권을 지금 사용해도 되는 것인지를 확신할 수 없었습니다.

스테이지를 클리어해 나가다가 클리어가 불가능 해졌을 때 무적권 사용?

위의 아이디어는 무적권을 사용하는 시점을 확정할 수 없다는 점이 문제였습니다.

그래서 이 아이디어를 생각해보았지만, 문제점이 있었습니다.

ex) n = 7, k = 2, enemy = [4,3,1,1,1,1,1,1,1] 인 경우

1. 1번, 2번 스테이지 클리어 후 3번, 4번 스테이지에서 무적권 사용

2. 1번, 2번 스테이지에서 무적권 사용 후 3 ~ 9스테이지 클리어

위의 경우에서, 최상의 경우는 당연히 2번이지만 이 방법을 사용하면 1번의 결과를 갖게됩니다.

위의 두 가지 아이디어를 합치다

위의 두 가지 아이디어는 각각 문제점이 존재했기 때문에 사용할 수 없었습니다.

하지만 잘 생각해보면, 두 아이디어는 서로 연관되어 있습니다.

두 번째 아이디어의 예시에서 3번 스테이지를 클리어할 수 없고 그렇기 때문에 3번 스테이지에서 무적권을 사용했지만, 이를 1번 스테이지에서 미리 사용하고 왔다면 더 많은 스테이지를 클리어할 수 있었을 것입니다. (1번 아이디어)

그래서 저는 이런 방법을 사용했습니다.

1. Max Heap을 사용하여 이전 까지 클리어 한 스테이지들의 enemy[i]를 저장합니다.

2. 더 이상 클리어가 불가능(2번 아이디어)하고 무적권이 남아있는 상태라면, Max Heap에서 heappop을 하여 지금 까지의 스테이지 중 enemy[i]가 가장 큰 스테이지의 enemy[i] 만큼을 n에 더해주어 마치 그 스테이지에서 무적권을 이미 사용하고 온 것 처럼 만들어 줍니다. (1번 아이디어)