[알고리즘] 백준 16637 - 괄호 추가하기 (C++)

[문제 링크] : https://www.acmicpc.net/problem/16637

#include <iostream>
using namespace std;

int N;
string S;
int Ans = -1234567890;

int calc(int a, int b, char op){
    int res = a;
    if(op == '+'){
        res += b;
    }
    else if(op == '-'){
        res -= b;
    }
    else if(op == '*'){
        res *= b;
    }
    return res;
}

void solve(int idx, int val){
    if(idx > N - 1){
        Ans = max(Ans, val);
        return;
    }

    char op;
    if(idx == 0){
        op = '+';
    }
    else{
        op = S[idx - 1];
    }

    if(idx + 2 < N){
        int tmp = calc(S[idx] - '0', S[idx + 2] - '0', S[idx + 1]);
        solve(idx + 4, calc(val, tmp, op));
    }

    solve(idx + 2, calc(val, S[idx] - '0', op));
    return;
}

int main(){
    cin >> N >> S;

    solve(0, 0);

    cout << Ans << "\n";

    return 0;
}