[BOJ] 14888번 연산자 끼워넣기

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, a[101];
vector <int> oper;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < 4; i++) {
        int operCnt;
        cin >> operCnt;
        for (int j = 0; j < operCnt; j++)
            oper.push_back(i);//연산자수만큼 벡터에 넣는다
    }
    int maxNum = -2e9;
    int minNum = 2e9;
    do {
        int num = a[0];
        for (int i = 1; i < n; i++) {
            int cal = oper[i - 1];
            if (cal == 0) num += a[i];
            else if (cal == 1) num -= a[i];
            else if (cal == 2) num *= a[i];
            else num /= a[i];
        }
        maxNum = maxNum > num ? maxNum : num;
        minNum = minNum < num ? minNum : num;
    } while (next_permutation(oper.begin(), oper.end()));
    cout << maxNum << '\n' << minNum;
}

#include <iostream>
#include <vector>
using namespace std;
int n, a[101], oper[4];
int maxNum = -2e9;
int minNum = 2e9;
void dfs(int cnt, int num) {
    if (cnt == n - 1) {
        maxNum = maxNum > num ? maxNum : num;
        minNum = minNum < num ? minNum : num;
        return;
    }
    if (oper[0] > 0) {
        oper[0] -= 1;
        dfs(cnt + 1, num + a[cnt + 1]);
        oper[0] += 1;
    }
    if (oper[1] > 0) {
        oper[1] -= 1;
        dfs(cnt + 1, num - a[cnt + 1]);
        oper[1] += 1;
    }
    if (oper[2] > 0) {
        oper[2] -= 1;
        dfs(cnt + 1, num * a[cnt + 1]);
        oper[2] += 1;
    }
    if (oper[3] > 0) {
        oper[3] -= 1;
        dfs(cnt + 1, num / a[cnt + 1]);
        oper[3] += 1;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < 4; i++) {
        int operCnt;
        cin >> oper[i];
    }
    dfs(0, a[0]);
    cout << maxNum << '\n' << minNum;
}