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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

프로그래머스

디펜스 게임

문제

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  • 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

제한사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

 

풀이

처음에는 재귀함수를 통해서 완전탐색을 돌렸다.

결과는 처참히 시간초과 발생...

 

다시 고민한 결과, 이 문제를 풀기 위한 키카드는 이분탐색이었다.

(물론, 너무 어렵게 생각한 것일 수도 있다... 더 쉬운 풀이법이 존재할지도...)

 

늘 그랬듯, 이분 탐색의 시작 지점은 0으로, 끝 지점은 이번에는 enemy 배열의 길이로 해준다.

mid의 의미는, mid + 1 라운드라는 뜻이다.

즉, enemy[0]부터 enemy[mid] 까지의 적들을 모두 격파할 수 있는지 없는지에 따라 mid의 값을 갱신해준다.

 

다만, 무적권이라는 변수가 있다. 그렇기 때문에 0부터 mid까지의 적들 중 크기가 큰 적들은 무적권을 써서 피해없이 패스해줘야한다. 이를 위해서 0부터 mid 사이에 있는 값들을 계속 탐색하며 비교해줘야 하는데, 일반적인 for문으로 찾으면 오래 걸리므로, 우선순위 큐를 이용해서 최댓값을 탐색한다.

 

이렇게 하니, 드디어 시간 초과가 발생하지 않는다. 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    int e_size = enemy.size();

    if (k >= e_size) {
        return e_size;
    }

    int start = 0;
    int end = e_size - 1;
    int mid = (start + end) / 2;

    priority_queue<int> pq;
    while (start <= end) {
        for (int i = 0; i <= mid; i++) {
            pq.push(enemy[i]);
        }

        // 무적권을 다 쓰고도 적들이 남아있음?
        // ㅇㅇ면 그 보다 더 적거나 같은 라운드 견디기 가능.
        if (pq.size() >= k) {
            for (int i = 0; i < k; i++) {
                pq.pop();
            }
            long long sum = 0;
            while (!pq.empty()) {
                sum += pq.top();
                pq.pop();
            }

            // 무적권 다 쓰고 현재 병사 수가 남아있는 적들 수 보다 많으면 못 견딤.
            // = 버틸 수 있는 라운드가 줄어들어야함
            if (sum > n) {
                end = mid - 1;
            }
            else {
                start = mid + 1;
                answer = max(answer, mid + 1);
            }
        }
        // ㄴㄴ면 더 많은 라운드 견디기 가능.
        else {
            while (!pq.empty()) {
                pq.pop();
            }
            start = mid + 1;
        }
        mid = (start + end) / 2;
    }

    return answer;
}