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

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

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

틀린 풀이 1

• 합계: 56.3 / 100.0

#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

int getMaxRounds(int n, int k, vector<int> enemy){
    //<n, <k, rounds>>
    priority_queue<pair<int, pair<int, int>>> q;
    q.push({n, {k, 0}});
    
    //<n, <k, rounds>>
    set<pair<int, pair<int, int>>> visited;
    
    int maxRounds = 0;
    while(!q.empty()){
        int curN = q.top().first;
        int curK = q.top().second.first;
        int curRound = q.top().second.second;
        q.pop();
        
        if(visited.find({curN, {curK, curRound}}) != visited.end()) continue;
        visited.insert({curN, {curK, curRound}});
        
        maxRounds = max(maxRounds, curRound);
        
        //모든 게임에서 승리할 수 있는 경우 -> 최댓값 결정됨
        if(curRound >= enemy.size()) break;
        
        if(curK > 0)
            q.push({curN, {curK-1, curRound+1}});
        
        if(enemy[curRound] <= curN)
            q.push({curN - enemy[curRound], {curK, curRound+1}});
    }
       
    return maxRounds;
}

int solution(int n, int k, vector<int> enemy) {
    int answer = getMaxRounds(n, k, enemy);
    return answer;
}

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	통과 (3.14ms, 4.34MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (4.67ms, 38.5MB)
테스트 12 〉	통과 (849.89ms, 95.5MB)
테스트 13 〉	통과 (0.01ms, 4.21MB)
테스트 14 〉	통과 (0.01ms, 4.21MB)
테스트 15 〉	통과 (0.01ms, 4.21MB)
테스트 16 〉	통과 (0.01ms, 4.21MB)
테스트 17 〉	통과 (0.01ms, 4.14MB)
테스트 18 〉	통과 (0.01ms, 4.14MB)
테스트 19 〉	통과 (0.01ms, 4.21MB)
테스트 20 〉	통과 (0.01ms, 4.21MB)
테스트 21 〉	통과 (0.01ms, 4.21MB)
테스트 22 〉	통과 (0.01ms, 3.59MB)
테스트 23 〉	통과 (201.04ms, 18.6MB)
테스트 24 〉	통과 (35.86ms, 6.9MB)
테스트 25 〉	통과 (23.29ms, 6.07MB)
테스트 26 〉	실패 (시간 초과)
테스트 27 〉	실패 (시간 초과)
테스트 28 〉	통과 (0.39ms, 3.68MB)
테스트 29 〉	실패 (시간 초과)
테스트 30 〉	통과 (2749.02ms, 171MB)
테스트 31 〉	실패 (시간 초과)
테스트 32 〉	실패 (시간 초과)

틀린 풀이 2

• 합계: 65.6 / 100.0

#include <string>
#include <vector>
#include <algorithm>
#include <iostream> 

using namespace std;

typedef long long ll;

//내림차순 정렬
bool cmp(int a, int b){
    return a > b;
}

int solution(int n, int k, vector<int> enemy) {
    
    ll sum = 0;
    for(int i = 0; i<enemy.size(); ++i){
        sum += enemy[i];
    }
    
    //최소 k개의 경기는 이길 수 있음
    int answer = k;
    
    for(int len = enemy.size(); len> k; --len){
        if(len != enemy.size()){
            sum -= enemy[len];
        }
        vector<int> enemyCopy(enemy.begin(), enemy.begin() + len);
        sort(enemyCopy.begin(), enemyCopy.end(), cmp);
        
        int need = sum;
        for(int i = 0; i<k; ++i){
            need -= enemyCopy[i];
        }
        
        if(need <= n){
            answer = len;
            break;
        }
    }
    
    return answer;
}

테스트 1 〉	통과 (2548.46ms, 4.21MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	통과 (0.03ms, 4.2MB)
테스트 6 〉	실패 (94.30ms, 42.2MB)
테스트 7 〉	실패 (71.08ms, 40.4MB)
테스트 8 〉	실패 (68.23ms, 40.4MB)
테스트 9 〉	실패 (68.99ms, 40.4MB)
테스트 10 〉	통과 (69.53ms, 40MB)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	통과 (0.01ms, 4.21MB)
테스트 14 〉	실패 (0.01ms, 4.07MB)
테스트 15 〉	통과 (0.01ms, 4.21MB)
테스트 16 〉	통과 (0.01ms, 4.2MB)
테스트 17 〉	통과 (0.01ms, 3.68MB)
테스트 18 〉	통과 (0.01ms, 4.13MB)
테스트 19 〉	통과 (0.01ms, 4.22MB)
테스트 20 〉	통과 (0.01ms, 4.19MB)
테스트 21 〉	통과 (0.01ms, 4.2MB)
테스트 22 〉	실패 (0.01ms, 4.13MB)
테스트 23 〉	통과 (0.04ms, 4.19MB)
테스트 24 〉	통과 (0.04ms, 4.19MB)
테스트 25 〉	통과 (0.21ms, 3.68MB)
테스트 26 〉	통과 (0.23ms, 3.67MB)
테스트 27 〉	통과 (0.17ms, 4.21MB)
테스트 28 〉	통과 (0.03ms, 4.2MB)
테스트 29 〉	통과 (0.01ms, 4.13MB)
테스트 30 〉	통과 (0.48ms, 3.75MB)
테스트 31 〉	통과 (0.16ms, 4.24MB)
테스트 32 〉	통과 (0.36ms, 4.2MB)