[백준, 백트래킹] 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

접근법

DFS로 풀이하고, 두번째 줄에 주어지는 입력의 수 만큼 연산이 완료되면 최소값과 최대값을 비교한다.

이 때 최솟값은 -10억 미만이 될 수 없으므로 10억, 최댓값은 10억을 초과 할 수 없으므로 -10억으로 초기화한다.

---

풀이

 

위의 그림 같이 연산자를 앞에 것 부터 순차적으로 번갈아가며 사용했다.

예를들면 깊이가 1일 때 '+', '-', 'x', '/' 연산자를 모두 사용해야 하므로 연산자의 개수를 감소 시키고 재귀 함수를 호출한 뒤 연산자 개수를 다시 증가시켰다.

    for (int i = 0; i < operators.size(); ++i)
    {
        if (0 < operators[i])
        {
            long long backup_sum = sum;

            operators[i] -= 1;

            if (i == 0)
            {
                sum += numbers[n];
            }
            else if (i == 1)
            {
                sum -= numbers[n];
            }
            else if (i == 2)
            {
                sum *= numbers[n];
            }
            else if (i == 3)
            {
                if (0 > sum)
                {
                    sum *= -1;
                    sum /= numbers[n];
                    sum *= -1;
                }
                else
                    sum /= numbers[n];
            }
            calculate(numbers, operators, n + 1, sum);
            sum = backup_sum;
            operators[i] += 1;
        }
    }

---

전체 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int max_depth = 0;
long long min_answer = 1'000'000'000;
long long max_answer = -1'000'000'000;

void calculate(const vector<int>& numbers, vector<int>& operators, int n, long long sum)
{
    if (n == max_depth)
    {
        max_answer = max(sum, max_answer);
        min_answer = min(sum, min_answer);
    }

    for (int i = 0; i < operators.size(); ++i)
    {
        if (0 < operators[i])
        {
            long long backup_sum = sum;

            operators[i] -= 1;

            if (i == 0)
            {
                sum += numbers[n];
            }
            else if (i == 1)
            {
                sum -= numbers[n];
            }
            else if (i == 2)
            {
                sum *= numbers[n];
            }
            else if (i == 3)
            {
                if (0 > sum)
                {
                    sum *= -1;
                    sum /= numbers[n];
                    sum *= -1;
                }
                else
                    sum /= numbers[n];
            }
            calculate(numbers, operators, n + 1, sum);
            sum = backup_sum;
            operators[i] += 1;
        }
    }


}
int main()
{
    int N = 0;
    cin >> N;
    max_depth = N;

    vector<int> numbers = vector<int>(N, 0);
    vector<int> operators = vector<int>(4, 0);

    for (int i = 0; i < N; ++i)
        cin >> numbers[i];

    for (int i = 0; i < 4; ++i)
        cin >> operators[i];

    calculate(numbers, operators, 1, numbers[0]);

    cout << max_answer << endl;
    cout << min_answer << endl;

    return 0;
}