프로그래머스 (Java) 140285 : 디펜스 게임

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

프로그래머스

---

풀이

데이터의 수가 작지 않아서 dp를 생각했는데, 정리할 수 있는 기준이 생각나지 않았다.

더 생각해보니 일단 막을 수 있는 만큼 병사를 막고, 안 되는 케이스에만 무적권을 사용해야겠다고 생각했다.

우선순위 큐를 사용, 막을 수 없을 때는 현재까지 나온 값 중 가장 큰 값에 무적권을 사용했다고 판단, 병사를 복구하여 다시 탐색했다.

 

---

Java 코드

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int answer = enemy.length;
        
        for (int i = 0; i < enemy.length; i++) {
            n -= enemy[i];
            pq.add(enemy[i]);
            if (n < 0) {
                if (0 < k && !pq.isEmpty()) {
                    n += pq.poll();
                    k--;
                }
                else {
                    return i;
                }
            }
        }
        return answer;
    }
}