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

 

프로그래머스

 

📄 문제

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

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

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

 

📝 풀이

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

using namespace std;

int solution(int n, int k, vector<int> enemy) {
	int answer = 0;
	int sum = 0;
	priority_queue<int> q;

	int i = 0;
	// sum이 n을 초과하기 전까지 큐에 삽입
	for (; i < enemy.size(); ++i)
		if (sum + enemy[i] > n)
			break;
		else
		{
			sum += enemy[i];
			q.push(enemy[i]);
		}
	
	// 무적권을 모두 사용할때까지 검사
	for (; i < enemy.size() && k; ++i)
	{
		// 큐에 삽입
		q.push(enemy[i]);
		sum += enemy[i];

		// sum이 n을 초과(병사가 부족한경우)
		if (sum > n)
		{
			// k(무적권)을 사용하여 가장 병사가 많이 필요한 경우 제거
			sum -= q.top();
			q.pop();
			++answer;
			--k;
		}
	}

	// q에 남아있는 수 더하기
	answer += q.size();

	// 무적권을 모두 사용했을때, 나머지 라운드를 최대한 시도
	for (; i < enemy.size(); ++i)
	{
		// 병사 수가 초과되었다면 끝내기
		if (sum + enemy[i] > n)
			break;

		sum += enemy[i];
		++answer;
	}

	return answer;
}

• 우선순위 큐를 이용하여 문제를 해결합니다.
• 무적권을 사용할때에는 현재 처리하고자 하는 라운드에서 가장 병사가 많이 필요한 값을 무적권을 사용해야 최적의 답을 구할 수 있습니다.