알고리즘
[알고리즘] 백준 16637 - 괄호 추가하기 (C++)
blueberrysoda
2025. 1. 25. 23:20
[문제 링크] : 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;
}