[C++] 프로그래머스 Lv2 디펜스 게임
문제 설명
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 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 해주세요.
입출력 예
n k enemy result
7 3 [4, 2, 4, 5, 3, 3, 1] 5
2 4 [3, 3, 3, 3] 4
입출력 예 설명
입출력 예#1
1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.
입출력 예#2
준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.
문제 풀이 요점
- 가지고 있는 병사를 소모하다가 병사가 모자란 경우가 생길 때를 찾아야한다.
- 모자란 경우 그 전까지의 전투에서 가장 많은 병사를 찾아 그 라운드에 무적권을 소모한다.
- 무적권은 단지 대상 라운드에서 소모한 병사를 취소하는 것이다.
- 가장 많은 병사를 소모한 라운드를 매번 찾아도 되지만 정렬이 되어 있는 자료가 있다면 시간절약이된다.
- 정렬을 위해서는 우선순위 큐 등을 사용한다. (속도를 위해서 무적권 최대 개수까지만 저장해 놓는것이 좋다.)
#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 army = n;
int round = enemy.size();
for (int i = 0; i < round; i++)
{
int enemyCount = enemy[i];
pq.push(enemyCount);
army -= enemyCount;
// 남은 병사가 없는 경우
if (army < 0)
{
// 무적권이 남아있을 경우
if (k > 0)
{
// 라운드를 치르면서 가장 많은 적들을 골라 무적권을 사용
int maxValue = pq.top();
pq.pop();
army += maxValue; // 가장 많은 적들만큼 취소했으니 병사 증가
k--; // 무적권 감소
}
else
{
// 무적권이 남아있지 않기 때문에 라운드 끝
break;
}
}
answer++;
}
return answer;
}
실패내역
멀티셋을 사용하여 푼 경우
// 32개의 테스트 중 5개 실패
#include <string>
#include <vector>
#include <set>
using namespace std;
int solution(int n, int k, vector<int> enemy) {
int answer = 0;
multiset<int, greater<int>> descValue; // 내림차순 중복허용 set
multiset<int>::iterator iter;
int army = n;
for (int i = 0; i < enemy.size(); i++)
{
descValue.insert(enemy[i]);
army -= enemy[i];
// 남은 병사가 없는 경우
if (army <= 0)
{
// 무적권이 남아있을 경우
if (k > 0)
{
// 라운드를 치르면서 가장 많은 적들을 골라 무적권을 사용
iter = descValue.begin();
int maxValue = *iter;
army += maxValue; // 가장 많은 적들만큼 취소했으니 병사 증가
k--; // 무적권 감소
descValue.erase(iter); // 라운드 제거
}
else
{
// 무적권이 남아있지 않기 때문에 라운드 끝
break;
}
}
answer++;
}
return answer;
}
'Thinking > Programmers' 카테고리의 다른 글
C++ 프로그래머스 Lv3 하노이의 탑 (0) | 2023.09.16 |
---|---|
C++ 프로그래머스 Lv1 추억 점수 (0) | 2023.09.15 |
C++ 프로그래머스 Lv3 연속 펄스 부분 수열의 합 (0) | 2023.09.15 |
C++ 프로그래머스 Lv2 요격 시스템 (0) | 2023.09.15 |
C++ 프로그래머스 Lv1 달리기 경주 (0) | 2023.09.15 |