[ 프로그래머스 ] 142085 디펜스 게임

Link | 프로그래머스 142085번 문제 : 디펜스 게임

📌 About

BFS으로 이 문제를 해결할 수도 있겠지만 그러면 경우의 수가 너무 많아진다.

DP로 한 번의 탐색으로 해결할 수 있다.

📌 Solution

각각의 라운드를 차례대로 도전한다.

도전한 라운드에서 출몰하는 적의 수만큼 나의 병사 수를 줄인다.

추가로 우선순위 큐에 출몰한 적의 수를 삽입한다. (내림차순 우선순위 큐이다.)

만약 남은 병사의 수가 음수이면 무적권을 사용할 수 있는지 확인한다.

무적권을 사용할 수 있다면 우선순위 큐에서 최대 출몰 적을 가져와서 병사의 수로 추가한다.

해당 최대 출몰 적을 마주한 라운드에서 무적권을 사용한 것으로 간주하는 것이다.

만약 무적권을 사용할 수 없다면 이전 라운드가 최대 공략 가능 라운드이다.

만약 모든 적을 소탕하였다면 라운드 수만큼 공략한 것이다.

📌 Code

GitHub Repository

class Solution {
    public int solution(int n, int k, int[] enemy) {
        Queue<Integer> enemies = new PriorityQueue<>(Comparator.reverseOrder());
        for (int round = 1; round <= enemy.length; round++) {
            int e = enemy[round - 1];
            n -= e;
            enemies.offer(e);
            if (n < 0 && k > 0 && !enemies.isEmpty()) {
                n += enemies.poll();
                k--;
            } else if (n < 0) return round - 1;
        }
        return enemy.length;
    }
}