디펜스 게임은 보유한 병사
n
명으로 연속되는 적의 공격을 순서대로 막는 게임입니다.디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
처음에 병사n
명을 가지고 있습니다.
매 라운드마다enemy[i]
마리의 적이 등장합니다.
남은 병사 중enemy[i]
명 만큼 소모하여enemy[i]
마리의 적을 막을 수 있습니다.
예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대k
번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수n
, 사용 가능한 무적권의 횟수k
,
매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열enemy
가 매개변수로 주어집니다.
몇 라운드까지 막을 수 있는지return
하도록solution
함수를 완성해주세요.
public class DefenseGameSolver
{
public static int Solution(int n, int k, int[] enemy)
{
int soldierCount = n;
int chanceCount = k;
//정렬된 상태를 유지하므로 가장 큰 값을 찾기에 유리
SortedList<int, int> prevEnemyCounts = new SortedList<int, int>();
for (int i = 0; i < enemy.Length; i++)
{
int enemyCount = enemy[i];
soldierCount -= enemyCount;
if (!prevEnemyCounts.TryAdd(enemyCount, 1))
{
prevEnemyCounts[enemyCount]++;
}
//병사의 수가 현재 적의 수보다 적음
if (soldierCount < 0)
{
//사용할 찬스의 수가 없으면 현재 라운드를 반환
if(chanceCount == 0)
return i;
//찬스를 사용할 경우
//찬스 횟수를 차감
chanceCount--;
//key 값들은 오름차순으로 정렬되어 있으므로 가장 끝에 있는 값이 가장 작은 값
int prevMaxEnemyCount = prevEnemyCounts.Keys[prevEnemyCounts.Count - 1];
soldierCount += prevMaxEnemyCount;
if (prevEnemyCounts[prevMaxEnemyCount] == 1) // 해당 적의 수가 1번만 등장했으면 제거
{
prevEnemyCounts.Remove(prevMaxEnemyCount);
}
else // 여러 번 등장했으면 카운트만 감소
{
prevEnemyCounts[prevMaxEnemyCount]--;
}
}
}
return enemy.Length;
}
}
무적권을 최적의 상황에서 사용하는 방법
- 매번 적을 마주칠 때 해당 상황이 최적의 상황인지는 판단할 수 없음
(가장 적이 많을 때 무적권을 사용해야하나 해당 적이 가장 많은 숫자인지 알 수 없음)- 따라서 남은 병사의 수가 0 이하가 되어 무적권을 사용해야하는 상황일 때 기존에 가장 많았던 적이 만났을 때 무적권을 사용한 것으로 치는 것으로 최적으로 사용하는 상황을 구현
key
값들이 정렬되어 있는 SortedList
자료형을 사용if (!prevEnemyCounts.TryAdd(enemyCount, 1))
{
prevEnemyCounts[enemyCount]++;
}
prevEnemyCounts
에 있다면 등장 횟수를 증가시키고 없다면 추가int prevMaxEnemyCount = prevEnemyCounts.Keys[prevEnemyCounts.Count - 1];
Key
중에서 가장 뒤에 있는 가장 큰 값을 가져와 반영