[Programmers] Lv2. 디펜스 게임 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

처음에는 DP로 무적권 스킬을 사용했을 경우와 안 했을 경우의 데이터들을 저장하여 풀어나가려고 했는데, 무적권 스킬 개수(k)와 병사들 수(n)가 같은 게 아니라서 그렇게 할 수가 없더라구요. 그래서 스택(Stack)을 이용해서 큰 숫자를 무적권 스킬로 스킵하는 형식으로 코드를 작성했었는데, 이것 역시 최적이라는 보장이 없었습니다.

 

방법은 우선순위 큐(Priority Queue, heap)였네요. 왜 이 생각을 못 했을까요. 방법은 간단합니다.

 

• 현재 병사 수(n)가 현재 라운드의 적의 수(enemy[i])보다 작고, 무적권 스킬 개수(k)가 0개라면 루프 종료
  • 그게 아니라면, enemy[i]를 우선 순위 큐에 넣고, n -= enemy[i]를 해줍니다.
  • 라운드도 +1 해줍니다.
• 사용 가능한 병사 이상으로 사용 했다면(n < 0), 우선 순위 큐에서 하나씩 pop하여 n에 더해줍니다.
  • pop을 할 때마다 k를 1개씩 줄여줍니다.
  • k > 0이고, n >= 0이 되었다면 루프를 종료
  • k == 0이고,  n < 0이라면 현재 라운드는 빼고 루프 종료
• 모든 라운드를 클리어했다면 enemy 배열의 길이를 리턴하고, 아니라면 카운트 한 라운드 수 리턴

 

✏️소스 코드 및 결과

#include <vector>
#include <queue>
using namespace std;

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

	for (; i < enemy.size(); i++) {
		if (n < enemy[i] and k == 0)
			break;

		enemies.emplace(enemy[i]);
		n -= enemy[i];
		answer++;

		while (!enemies.empty() and n < 0) {
			if ((k == 0 and n < 0)) {
				answer--;
				break;
			}

			n += enemies.top();
			enemies.pop();
			k--;
		}
	}

	return i == enemy.size() ? enemy.size() : answer;
}