[BOJ][C#] 14888 연산자 끼워넣기

📕 문제

📌 링크

📗 접근 방식

DFS를 활용
1. 각 단계에서 현재까지의 결과를 계산하고 최대값과 최소값을 최신화
2. 모든 연산자 조합을 시도하고 최종 최대값과 최소값을 출력

📘 코드

using System.Text;

namespace BOJ
{

    class No_13335
    {
        static int n;
        static int myMax = int.MinValue;
        static int myMin = int.MaxValue;
        static int[] nums, oper;

        static void Main()
        {
            n = int.Parse(Console.ReadLine());
            nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            oper = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            DFS(1, nums[0]);

            StringBuilder sb = new StringBuilder();
            sb.AppendLine(myMax.ToString());
            sb.AppendLine(myMin.ToString());
            Console.Write(sb);
        }

        static void DFS(int idx, int num)
        {
            if(idx == n)
            {
                if (num > myMax) myMax = num;
                if (num < myMin) myMin = num;
                return;
            }

            for(int i=0 ;i<4 ;i++)
            {
                if(oper[i] > 0)
                {
                    oper[i]--;
                    if(i == 0) DFS(idx + 1, num + nums[idx]);
                    else if(i == 1) DFS(idx + 1, num - nums[idx]);
                    else if(i == 2) DFS(idx + 1, num * nums[idx]);
                    else DFS(idx + 1, num / nums[idx]);
                    oper[i]++;
                }
            }
        }
    }
}

📙 오답노트

📒 알고리즘 분류

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