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

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

 

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

프로그래머스

---

 

해결전략

 

우선순위큐 Priority Queue

---

 

처음 시도한 코드 - DFS 시간초과

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int answer;

void DFS(int n, int k, vector<int> e, int cnt)
{
    if (cnt == e.size() || k < 0 || k == 0 && n - e[cnt] < 0) {
        answer = max(answer, cnt);
        return;
    }

    if (n >= e[cnt]) 
        DFS(n - e[cnt], k, e, cnt + 1);
    if (k > 0) 
        DFS(n, k - 1, e, cnt + 1);
}

int solution(int n, int k, vector<int> e) {
    
    DFS(n, k, e, 0);

    return answer;
}

 

---

 

정답 코드

 

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

int solution(int n, int k, vector<int> e)
{
    int answer = e.size(); // 모든 라운드를 통과하는 경우를 초기값으로 설정
    int sum = 0;

    priority_queue<int, vector<int>, greater<int>> pQ; // 오름차순
    
    for (int i = 0; i < e.size(); i++)
    {
        pQ.push(e[i]);

        if (pQ.size() > k) // 무적권보다 개수보다 크게 쌓이게되면
        {
            sum += pQ.top(); // 가장 작은값(=무적권을 사용하지 않고 무찌른 적 병사 수)을 더함 
            pQ.pop();       // 해당 경우는 무적권을 안 쓴 경우이니 빼준다
        }

        if (sum > n) { // 해치운 적의 수의 합 > 처음에 주어진 병사 수
            answer = i;
            break;
        }
    }

    return answer;
}

int main() {
    vector<int> testcase1 = { 4, 2, 4, 5, 3, 3, 1 };
    vector<int> testcase2 = { 3, 3, 3, 3 };
    vector<int> testcase3 = { 99, 1, 99 };
    vector<int> testcase4 = { 2, 1, 5, 1 };
    vector<int> testcase5 = { 2, 1, 99, 99 };
    vector<int> testcase6 = { 2, 2, 2, 2, 3, 3, 1 };
    vector<int> testcase7 = { 2, 2, 2, 2, 2, 10 };
    vector<int> testcase8 = { 2, 2, 2, 2, 10 };
    vector<int> testcase9 = { 3, 4 };

    cout << "Result = " << solution(7, 3, testcase1) << "\n"; // 5
    cout << "Result = " << solution(2, 4, testcase2) << "\n"; // 4
    cout << "Result = " << solution(5, 2, testcase3) << "\n"; // 3
    cout << "Result = " << solution(7, 1, testcase4) << "\n"; // 4
    cout << "Result = " << solution(7, 2, testcase5) << "\n"; // 4
    cout << "Result = " << solution(1, 6, testcase6) << "\n"; // 7
    cout << "Result = " << solution(10, 1, testcase7) << "\n"; // 6
    cout << "Result = " << solution(10, 1, testcase8) << "\n"; // 5
    cout << "Result = " << solution(3, 1, testcase9) << "\n"; // 2

    return 0;
}