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

문제

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

프로그래머스

---

📕문제 풀이

무적권을 적절한 라운드에 사용해서 최대한 많은 라운드를 버텨야 한다.
따라서 무적권을 사용하는 라운드를 선정하는 방법이 중요하다!

📗초기 풀이 방식

초기 풀이 방식은 queue에 넣어서, 모든 경우의 수를 탐색했다.

하지만 N의 길이가 커서 시간초과가 났다.

초기 알고리즘은 이렇다.

queue에 원소를 계속 넣어서, 만약 가용가능한 병사의 수가 현재 라운드의 적의 수보다 적으면 무적권을 사용하고, 아니면 가용가능한 병사의 수를 감소시켰지만, N의 크기가 너무 커서 시간초과가 일어났다.

아마도 의미 없는 경우의 수가 queue에 너무 많이 들어간 것 같다.

따라서 풀이방식을 수정했다.

---

📗수정 풀이 방식

우선순위큐를 사용했다.

우선순위큐에는 적의 수를 넣어줬다.

그리고 적의 수를 넣어줄 때마다, n에서 감소시켰다.

만약에 넣어 줄 수 없다면 무적권을 사용해야 한다.

우선 무적권을 사용하려면 k는 0 이상이어야 한다.

무적권을 사용하는 상황은 두 가지 경우의 수가 있다.

1. 이전 라운드에서 너무 많은 병사를 상대해서, 현재 라운드에서 무적권을 사용하는 경우
2. 현재 라운드에서 너무나 많은 병사를 상대해야 해서 무적권을 사용하는 경우

그래서 우리는 이전 라운드의 상대한 병사의 수와 현재 라운드에서 상대할 병사의 수를 비교해야 한다.

우리는 적절한 라운드에서 무적권을 사용해서 라운드를 넘겨야 하는 게 목표입니다.

최대한 많은 라운드를 버텨야 하기 때문입니다.

현재 내가 가용가능한 인원이 10명이라고 가정합시다.

1라운드에서 7명을 상대해서 3명이 남았고,

2라운드에서는 9명을 상대해야 합니다.

그러면 우리는 1라운드에서 무적권을 사용하는 것보다는 2라운드에서 무적권을 사용하는 것이 가용인원을 더 많이 남기는 방법일 것입니다.

따라서 비교하는 작업은 필수적이라고 할 수 있습니다.

만약 1라운드가 7명이고, 2라운드가 6명이면 1라운드에서 무적권을 사용하고, 2라운드를 그냥 상대하는 것이 좋은 방법일 것입니다.

그리고 만약 라운드 숫자가 무적권의 횟수보다 작거나 같다면 바로 라운드 숫자를 출력해 주면 됩니다.

라운드마다 무적권을 사용할 수 있으니까요^^

---

💻전체  코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int Size=0;
int answer = 0;
priority_queue<int, vector<int>>pq;
int funct(int n,int k, vector<int>enemy){

    for(int i=0; i<Size;i++){
        if(n>=enemy[i]){ //넣을 수 있다면 그냥 넣어준다.
            pq.push(enemy[i]);
            n-=enemy[i];
        }
        else{ //넣을 수 없다면 k를 검사.
            if(k!=0){ //무적권을 사용할 수 있다면
                k--; //k를 깎는다                
                if(!pq.empty()){
                    int now = pq.top();
                    pq.pop();                    
                    if(now>=enemy[i]){ //이전 라운드에서 적을 더 많이 상대한 경우            
                        n=n+now-enemy[i];
                        pq.push(enemy[i]); //무적권을 이전라운드에서 사용해서 이전라운드 무시하고, 현재 병사를 넣음.
                    }                    
                    else
                        pq.push(now); //그냥 무적권을 사용해서 이번라운드를 무시함.
                }
            }
            else 
                return i;
        }
    }
}
int solution(int n, int k, vector<int> enemy) {

    Size=enemy.size(); //라운드 수를 Size에 넣음.
    if(Size<=k){
        answer=Size;
        return answer;
    }
    else{
        answer=funct(n,k,enemy);        
    }
    return answer;
}