[C#] 디펜스 게임

Connected Brain·2025년 8월 7일
0

코딩 테스트

목록 보기
50/67

디펜스 게임

문제 설명

디펜스 게임은 보유한 병사 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 이하가 되어 무적권을 사용해야하는 상황일 때 기존에 가장 많았던 적이 만났을 때 무적권을 사용한 것으로 치는 것으로 최적으로 사용하는 상황을 구현

SortedList

  • 적이 가장 많은 상황을 찾을 수 있으어야 하므로 정렬된 값에 접근하는 것이 유리하므로 key 값들이 정렬되어 있는 SortedList 자료형을 사용
if (!prevEnemyCounts.TryAdd(enemyCount, 1))
{
	prevEnemyCounts[enemyCount]++;
}
  • 적의 숫자만큼 병사의 수를 감소시킨 후에 기존에 동일한 값을 가진 적의 숫자가 prevEnemyCounts에 있다면 등장 횟수를 증가시키고 없다면 추가
int prevMaxEnemyCount = prevEnemyCounts.Keys[prevEnemyCounts.Count - 1];
  • 찬스를 사용할 때는 Key 중에서 가장 뒤에 있는 가장 큰 값을 가져와 반영

0개의 댓글