백준) 14888.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <utility>

#define MAX 12
int n;
int num[MAX];
char ans[MAX];
bool visited[MAX];
int max = -2147483648;
int min = 2147483647;

int cal()
{
    int ret = num[0];

    for (int i = 0; i < n - 1; ++i)
    {
        if (ans[i] == '+')
            ret += num[i + 1];
        else if (ans[i] == '-')
            ret -= num[i + 1];
        else if (ans[i] == '*')
            ret *= num[i + 1];
        else if (ans[i] == '%')
            ret /= num[i + 1];
    }
    return (ret);
}

void sol(std::vector<char> &arr, int idx)
{
    if (idx == n - 1)
    {
        int t = cal();
        if (t < min)
            min = t;
        if (t > max)
            max = t;
        // for (int i = 0; i < n - 1; ++i)
        //     std::cout << ans[i] << " ";
        // std::cout << "\n";
        return;
    }
    for (int i = 0; i < n - 1; ++i)
    {
        if (!visited[i])
        {
            visited[i] = true;
            ans[idx] = arr[i];
            sol(arr, idx + 1);
            visited[i] = false;
        }
    }
}

int main()
{
    std::cin >> n;

    for (int i = 0; i < n; ++i)
        std::cin >> num[i];

    int plus, minus, mult, div;
    std::cin >> plus;
    std::cin >> minus;
    std::cin >> mult;
    std::cin >> div;

    std::vector<char> arr;
    for (int i = 0; i < plus; ++i)
        arr.push_back('+');
    for (int i = 0; i < minus; ++i)
        arr.push_back('-');
    for (int i = 0; i < mult; ++i)
        arr.push_back('*');
    for (int i = 0; i < div; ++i)
        arr.push_back('%');
    
    sol(arr, 0);

    std::cout << max << "\n";
    std::cout << min << "\n";
    // +-*% 조합 만들기
    // 그에 따라 숫자계산
}

회고

arr를 만들어서 연산자를 다 집어 넣는 방식이 별로 좋지 않다고 생각했지만, 아직 재귀와 백트레킹에 익숙하지 않아서 n과m(1) 문제를 풀때 사용했던 방식으로 밖에 생각이 나지 않았다.

문제를 통과하긴 했지만 그닥 좋은 방식은 아닌 듯 하여 다른 사람들의 풀이를 살펴보았는데
https://cryptosalamander.tistory.com/60 이분의 풀이가 가장 이해하기 쉬웠다.

#include <iostream>
using namespace std;

int N;
int operands[11]; // 수열 
int operators[4]; // 연산자의 개수
int mymin = 1000000001;
int mymax = -1000000001;
void getanswer(int result, int idx)
{
    if(idx == N)
    {
        if(result > mymax)
            mymax = result;
        if(result < mymin)
            mymin = result;
        return;
    }
    for(int i = 0; i < 4; i++)
    {
        if(operators[i] > 0)
        {
            operators[i]--; // 연산자 하나 사용했으므로 1개 줄여줌
            if(i == 0)
                getanswer(result + operands[idx], idx+1);
            else if(i == 1)
                getanswer(result - operands[idx], idx+1);
            else if(i == 2)
                getanswer(result * operands[idx], idx+1);
            else
                getanswer(result / operands[idx], idx+1);
            operators[i]++; // 다른 연산자를 사용할 것이므로 아까 줄였던 연산자 개수 늘려줌
        }
    }
    return;
}
int main() {
    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> operands[i];
    for(int i = 0; i < 4; i++)
        cin >> operators[i];
    getanswer(operands[0],1);
    cout << mymax << '\n';
    cout << mymin;
}

나처럼 연산자를 배열에 만들어 넣고 bool을 체크하는게 아니라 그냥 개수를 이용해 ++, -- 연산자로 bool의 역할을 했다. 그리고 배열의 위치에 따라 부호가 다른 것이니

operators[i]--; // 연산자 하나 사용했으므로 1개 줄여줌
            if(i == 0)
                getanswer(result + operands[idx], idx+1);
            else if(i == 1)
                getanswer(result - operands[idx], idx+1);
            else if(i == 2)
                getanswer(result * operands[idx], idx+1);
            else
                getanswer(result / operands[idx], idx+1);
            operators[i]++; // 다른 연산자를 사용할 것이므로 아까 줄였던 연산자 개수 늘려줌

이런 식으로 사용하셨다.
visited 말고도 체크할 수 있는게 있다는 사실을 기억하자.