디펜스 게임(해결)

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

매 라운드마다 경우는 2가지다. 무적권을 사용한다, 안 한다.

k(무적권의 개수)가 500,000이라 DFS를 통해 조합을 구하면 시간 초과가 날 거라 생각했지만 5분 뒤쯤 다른 방법이 번뜩 떠오르지 않아 일단 진행했다.
하지만 예상대로 다 시간 초과...

궁금한 게, 코딩테스트를 할 때 방법 고민의 시간은 얼마나 가지는 게 좋을까?
구현 아이디어 5분 구현 15분

풀이(시간 초과)

#include <string>
#include <vector>

using namespace std;
int answer = 0;

void DFS(int L, int n, int k, const vector<int>& enemy)
{
    // 적의 수가 우리 팀의 수보다 많다.
    if(L == enemy.size() || (enemy[L] > n && !k))
    {
        if(answer < L)
            answer = L;
        
        return;
    }
    else
    {
        // 경우는 2가지. 무적권을 쓰냐, 쓰지 않느냐.
        if(n - enemy[L] >= 0) DFS(L + 1, n - enemy[L], k, enemy);
        if(k) DFS(L + 1, n, k - 1, enemy);
    }
}

int solution(int n, int k, vector<int> enemy) {
    // 라운드, 우리 팀 수, 무적권 수.
    DFS(0, n, k, enemy);
    
    return answer;
}

---

풀이(53점)

결정 알고리즘인 파라메트릭 서치를 이용해 풀었다. 게시판에 있는 반례들과 테스트 케이스는 통과하는데 채점을 하면 반만 맞는다.

// 이진탐색. 결정 알고리즘. 파라메트릭 서치.
#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    
    priority_queue<int> pQ;
    
    int lp = 0, rp = enemy.size() - 1, mid = 0;
    int N = n, K = k;
    
    while(lp <= rp)
    {
        N = n;
        K = k;
        
        // mid 라운드까지 이길 수 있는지.
        mid = (lp + rp) / 2;
        
        // 우선순위 큐에 해당 라운드까지 적들의 수를 담음.
        for(int i = 0; i <= mid; ++i)
            pQ.push(enemy[i]);
        
        // 무적권의 개수만큼 많은 적들이 있는 라운드를 pop.
        while(true)
        {
            if(pQ.empty()) break;
            if(K == 0) break;
            pQ.pop();
            --K;
        }
        
        // N(우리 병사 수)에서 pQ의 원소들을 빼줌.
        while(true)
        {
            if(pQ.empty()) break;
            if(N < pQ.top()) break;
            
            int enemy_num = pQ.top();
            N -= enemy_num;
            pQ.pop();
        }
        
        // pQ의 사이즈가 1 이상이면 라운드를 깨지 못함.
        // pQ의 사이즈가 0이면 라운드 깰 수 있음.
        if(pQ.size() == 0)
        {
            lp = mid + 1;
        }
        else rp = mid - 1;
        while(!pQ.empty()) pQ.pop();
    }
    
    // 깰 수 있는 라운드가 없는 경우.
    if(!mid && rp == -1) mid = -1;
    
    // mid가 0부터 시작이므로 +1.
    return answer = mid + 1;
}

---

풀이

2가지를 고쳤다.

1. 처음에 lp와 rp를 0~enemy.size()-1로 초기화했더니 if(!mid && rp == -1) mid = -1; 같은 지저분한 코드가 필요해서 lp와 rp를 1~enemy.size()로 바꾸어주었다.

• 자연스럽게 return 때 더해주는 +1를 뺐다.

2. mid의 갱신 타이밍이 중요하다. while문의 마지막에서 갱신하지 않으면 n = 1, k = 0, [2, 2]일 때 답은 0이지만 출력은 1이다.

// 이진탐색. 결정 알고리즘. 파라메트릭 서치.
#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    
    priority_queue<int> pQ;
    
    int lp = 1, rp = enemy.size(), mid = (lp + rp) / 2;
    int N = n, K = k;
    
    while(lp <= rp)
    {
        N = n;
        K = k;
        
        // 우선순위 큐에 해당 라운드까지 적들의 수를 담음.
        for(int i = 0; i < mid; ++i)
            pQ.push(enemy[i]);
        
        // 무적권의 개수만큼 많은 적들이 있는 라운드를 pop.
        while(!pQ.empty() && K > 0)
        {
            pQ.pop();
            --K;
        }
        
        // N(우리 병사 수)에서 pQ의 원소들을 빼줌.
        while(!pQ.empty() && N >= pQ.top())
        {
            int enemy_num = pQ.top();
            N -= enemy_num;
            pQ.pop();
        }
        
        // pQ의 사이즈가 1 이상이면 라운드를 깨지 못함.
        // pQ의 사이즈가 0이면 라운드 깰 수 있음.
        if(pQ.size() == 0) lp = mid + 1;
        else rp = mid - 1;
        
        // pQ 비움.
        while(!pQ.empty()) pQ.pop();
        
        // mid 라운드까지 이길 수 있는지.
        mid = (lp + rp) / 2;
    }
    
    return answer = mid;
}