99클럽 코테 스터디 38일차 TIL , 디펜스 게임

문제

풀이

디펜스 게임을 하는데 적이 enemy에 적힌 순서대로 온다.

적의 수만큼 내 병력을 소모시켜서 막을 수 있다.

이 게임에는 스킬이 있는데 `무적권`이라는 스킬로 적의 수가 몇이든 턴을 넘길 수 있다.

주어지는 내 병력 n, 무적권 횟수 k, 적의 배열 enemy 가 주어질 때 최대 몇 번의 턴을 넘길 수 있는지 출력하면 된다.

풀이 1 - 오답

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> heapK = new PriorityQueue<>();
        PriorityQueue<Integer> heapN = new PriorityQueue<>(Collections.reverseOrder());
        int answer = 0;

        for(int i=0;i<enemy.length;i++){
            int tmp = enemy[i];
            if(n < tmp){
                if(k == 0){
                    if(heapN.isEmpty())break;
                    if(heapK.isEmpty()) break;
                    if(n + heapN.peek() - heapK.peek() < tmp) break;
                    else{
                        n += heapN.poll() - heapK.poll() - tmp;
                        answer++;
                    }
                }else{
                    k--;
                    heapK.add(tmp);
                    answer++;
                }
            }else{
                n -= tmp;
                heapN.add(tmp);
                answer++;
            }
        }

        return answer;
    }
}

 

내 병력에서 뺐을 경우와 무적권 스킬로 넘겼을 경우의 heap을 만들어 상황에 맞게 해주려고 했는데 열심히 추가한 17개의 테스트 케이스는 모두 통과하는데 답은 맞추지 못하고 43.8점이었다.

질문하기를 봐도 이유를 찾지 못해 질문을 남겨둔 상태다.

풀이 2 - 정답

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        if(k >= enemy.length) return enemy.length;	//무적권 스킬을 더 많이 쓸 수 있다면 return
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); //맥스힙
        int total = 0;
        
        for(int i=0;i<enemy.length;i++){
            heap.add(enemy[i]);	//힙에 추가
            total += enemy[i];	//total에 더해준다.
            
            if(total > n){	//total이 n보다 커지는 경우
                if(k > 0){	//k가 존재 할 경우 최대 값을 무적권 처리 해준다.
                    total -= heap.poll();
                    k--;
                }else{	//k가 없을 경우 현재 값을 return
                    return i;
                }
            }
        }
        return enemy.length;
    }
}

 

이게 가장 간단하고 그리디에 적합한 풀이라고 생각한다.

더해주고 값이 넘칠 때마다 k를 사용해서 계속해서 더해주다 무적권을 사용하지도 못하고 n도 넘을 경우에 return 해준다.

 

TIL

• greedy(탐욕법)