[BOJ][C#] 18429 근손실

📕 문제

📌 링크

📗 접근 방식

무식하게 모든 경우의 수를 찾는 방법밖에 떠오르지 않음
백트래킹을 통해 현재 플로우가 정답으로 가는 길이 아니라면 되돌아감

• 현재 플로우에서 체력이 500보다 아래로 내려간다면 리턴
• n개를 모두 체크한 경우 카운팅해줌 => 위에서 500 아래보다 내려간 경우 예외처리 해주기 때문에 굳이 한 번 더 체크할 필요 없음
• n개를 모두 탐색하며 사용하지 않은 인덱스를 들고 재귀

📘 코드

using System.Text;  
  
namespace BOJ  
{  
    static class Input<T>  
    {  
        public static T GetInput() => ConvertStringToType(Console.ReadLine());  
        public static T[] GetInputArray() => Array.ConvertAll(Console.ReadLine().Split(), Input<T>.ConvertStringToType);  
        private static T ConvertStringToType(string input) => (T)Convert.ChangeType(input, typeof(T));  
    }  
      
    class No_18429  
    {  
        static int answer = 0, n, k;  
        static int[] exerciseKits;  
        static bool[] used;  
          
        static void Main()  
        {  
            var inputs = Input<int>.GetInputArray();  
            n = inputs[0];  
            k = inputs[1];  
            exerciseKits = Input<int>.GetInputArray();  
            used = new bool[inputs[0]];  
  
            BackTracking(0, 0,500);  
  
            Console.WriteLine(answer);  
        }  
  
        static void BackTracking(int depth, int count, int curHp)  
        {  
            // 현재 값이 500보다 낮아진 경우  
            if (curHp < 500)  
            {  
                return;  
            }  
              
            if (count == n)  
            {  
                answer++;  
  
                return;  
            }  
              
            // 백트래킹  
            for (int i = 0; i < n; i++)  
            {  
                if (used[i] == false)  
                {  
                    count++;  
                    used[i] = true;  
                    BackTracking(i + 1, count, curHp - k + exerciseKits[i]);  
                    used[i] = false;  
                    count--;  
                }  
            }  
        }  
    }  
}

📙 오답노트

📒 알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹