[코테] 프로그래머스 - 디펜스 게임

1. 문제

• 총 병사 수(n)와 라운드 프리패스 가능한 횟수(k), 라운드 별 적군 수(enemy) 제공
  병사와 적군은 1:1 비율로 방어 가능, 방어에 사용시 차감
• 주어진 조건에서 최대로 방어 가능한 라운드 구하기
• 남은 병사 수가 해당 라운드의 적군 수보다 적고 프리패스 횟수도 0이라면 게임 종료

2. 풀이

• 완전탐색+백트래킹 고려
  ㅡ> Input의 크기를 생각했을 때, 시간복잡도를 맞추지 못할 확률이 높고, 더 나은 방법이 있을 것으로 추정
• 가장 많은 수의 적이 오는 라운드를 k개의 프리패스로 병력 손실 없이 패스하는 것이 최대 라운드까지 가는 방법
• k개의 최댓값 라운드를 추적할 수단이 필요
• 우선순위 큐를 최소 힙 형태로 활용

3. 코드

#include <bits/stdc++.h>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙
    long long answer = 0; 
    
    for(int i = 0; i < enemy.size(); i++) {
        pq.push(enemy[i]);
        
        // 최소 힙을 이용해 가장 큰 값을 지닌 k개의 라운드 추적 -> 초과분 합산하여 처리
        if(pq.size() > k) {
            answer += pq.top();
            pq.pop();
        }
        
        // 현재 합계가 n을 초과하면 더 진행 불가
        if(answer > n) {
            return i;
        }
    }
    
    // 여기까지 왔으면 모든 웨이브를 버틴 것
    return enemy.size();
}

• 우선 순위 큐를 최소 힙 형태로 활용
  ㅡ> top에 원소 중 가장 작은 값이 위치
  ㅡ> 조건을 달아 k개의 큰 값들을 큐에서 가지고 있도록 활용 가능
• 큐에서 꺼내는 원소는 병력을 이용해 막은 라운드에 해당하므로 손실되는 병력 누적 합산
• 손실된 병력의 누적값이 보유하고 있던 총 병력 수인 n보다 커지면 진행 불가로 현재 라운드 반환하며 종료
• 입력된 모든 라운드 순회했다면 전체 라운드 수 반환하며 종료

---

참고자료

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

프로그래머스