백준 16637문제

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

bool bracket[30];
vector<char> oper;
vector<int> num;
vector<int> new_num;
vector<char> new_oper;

int ANS = -1e9;

int cal(int a , int b , char oper){
    if(oper == '+') return a + b;
    else if(oper == '-') return a - b;
    else return a * b;
}

int fin_cal(int N){
    new_num.clear();
    new_oper.clear();

    for(int i=0 ;i<N/2 +1 ; i++){
        if(bracket[i] && i+1 < N/2+1){
            new_num.pb(cal(num[i],num[i+1],oper[i]));
            new_oper.pb(oper[i+1]);
            i++;
        }
        else{
            new_num.pb(num[i]);
            if(!oper.empty())
                new_oper.pb(oper[i]);
        }
    }

    int ret = new_num[0], size = new_num.size();

    for(int i = 0 ; i<size-1 ; i++)
        ret = cal(ret, new_num[i+1], new_oper[i]);


    return ret;
}


void rec(int N, int cur){
    int num_n = N/2+1;
    
    if(cur > num_n){
        ANS = max(ANS, fin_cal(N));
        return;
    }
    bracket[cur] = true;
    rec(N,cur+2);
    bracket[cur] = false;
    rec(N,cur+1);
}

int main(){
    ios_base::sync_with_stdio(false);

    int N;
    char arr[22] = {0,};
    cin >> N;
    cin >> arr;
    
    for(int i=0 ;i<N ;i++){
        char c = arr[i];
        if(c == '+' || c == '-' || c == '*') oper.pb(c);
        else num.pb(c-'0');
    }
    rec(N,0);
    cout << ANS << '\n';
    return 0;
}

백준 16637 문제 DFS 풀이입니다.