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

 

 

 

처음에는 enemy[i]의 합이 n보다 작으면 병사를 소모하고

크다면 무적권을 소모하도록

그냥 순서대로 소모되도록 했었다

 

이렇게 하면 예제도 잘 되고 다 되는줄 알았는데 

엄청 많이 틀렸다

 

반례를 생각해본 결과

 

n = 10, k = 2, enemy = [3, 7,10, 2, 5, 10]

일 경우에

 

내가 짠 대로 하면 3, 7에서 병사를 소모하고 10, 2에서 무적권을 사용하여 4번만에 종료된다

하지만 사실 3에서 병사 소모, 7, 10에서 무적권을 소모하고 2, 5에서 병사를 다시 소모한다면 

5번째 라운드까지 진행할 수 있다.

 

여기서 어떻게 해결을 해야할까 고민했다

조건문으로는 도저히 식이 구현되지 않고... 

따라서 하나의 배열같은 것을 따로 만들어서 거기서 뭔가를 해야겠다 !라고 생각하게 되었다

 

그래서 생각해낸것이 우선순위 큐

 

당연하게도 작은 숫자가 우선순위가 되는 큐를 하나 만들어서

거기에 차곡차곡 쌓고 

거기서 병사를 작은 숫자부터 소모하면 되는 것이었다

 

#include <queue>

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

	priority_queue<int, vector<int>, greater<>> que;

	for (int i = 0; i < enemy.size(); i++)
	{
		que.push(enemy[i]);

		if(que.size() > k)
		{
			sum += que.top();
			que.pop();
		}

		if (sum > n)
			return i;
		
	}

	return enemy.size();
}