[프로그래머스] 디펜스 게임 (C++)

문제 링크:https://school.programmers.co.kr/learn/courses/30/lessons/142085#

프로그래머스

1. 주의할 점

- 브루트포스 방식은 사용하지 않는다

 

2. 구현

- 병사를 사용하여 적을 막을 수 있을때까지 병사를 사용한다

- 적이 남은 병사보다 많은 경우, 현재 라운드 포함해서 가장 많이 사용한 병사에 대해 무적권을 사용한다. 이때, K가 0이라면 해당 라운드부턴 성공이 불가능하므로 for문을 종료한다

- Answer 초기값을 -1로 설정하여 갱신되지 않았다면 전체 라운드를 클리어할 수 있다고 판단한다

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = -1;
    priority_queue<int,vector<int>,less<int>> pq;
    
    for(int i=0;i<enemy.size();i++){
        int val = enemy[i];
        pq.push(val);
        n-=val;
        if(n<0){
            if(k==0){
                answer = i;
                break;
            }
            //무적권을 사용한다
            while(!pq.empty() && k>0 && n<0){
                n+=pq.top();
                k--;
                pq.pop();
            }
        }
    }
    return answer==-1 ? enemy.size() : answer;
}