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

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

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결전략

 

우선순위큐 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;
}