[알고리즘 문제 풀기] 연산자 끼워넣기(14888)

1. 문제 풀이 아이디어

• 재귀 함수를 활용해 가능한 모든 연산 순서를 탐색하여, 최댓값과 최솟값을 구해 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[] input = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int n = input[0];
    int[] a = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int[] op = Array.ConvertAll(sr.ReadLine().Trim().Split(), int.Parse);
    int min = int.MaxValue;
    int max = int.MinValue;
    MakeOps(1, a[0]);
    sw.WriteLine(max);
    sw.WriteLine(min);

    void MakeOps(int c, int x)
    {
        if (c == n)
        {
            min = Math.Min(min, x);
            max = Math.Max(max, x);
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            if (op[i] == 0) continue;
            op[i]--;
            int nx = x;
            if (i == 0) nx += a[c];
            else if (i == 1) nx -= a[c];
            else if (i == 2) nx *= a[c];
            else if (i == 3) nx /= a[c];
            MakeOps(c + 1, nx);
            op[i]++;
        }
    }
}

3. 정리

• MakeOps 함수는 재귀적으로 연산자 조합을 구성해나가며 중간 계산 결과를 유지하고, 최종적으로 최댓값과 최솟값을 갱신한다.

• 연산자는 각각 하나씩 소진해가며 재귀 호출하고, 호출이 끝나면 원래대로 복구(backtracking)한다.

• 모든 조합을 탐색한 후 최댓값과 최솟값을 출력해 문제를 해결한다.