[백준] 16637 괄호 추가하기

 

한번 풀어보려고했는데 한시간이나 걸렸따...

문제를 쉽게 해주기 위해 괄호는 하나의 연산자만 포함한다는걸 모르고 풀다가

나중에 보니 답이 다르게나온다~!

 

그리고 처음에 한자리수만 줘서 더 쉬운것같다

 

나처럼 복잡하게 푼 사람은 많이 없을듯..!

 

그럼 문제를 풀어보자!

우선 비트를 이용해서 짝수 인덱스인 숫자만 봐준다

괄호가 짝이 맞아야 하기 때문에 짝수개 있을 때만 넘겨준다!

110101이면 1~2 ,4~6이 괄호다!

 

괄호를 체크하고 solve 함수로 넘겨준다

그럼 solve는 괄호가 있는곳은 먼저 cal함수로 계산해주고 

마지막에 괄호가 없을 때를 계산해 답으로 넘겨준다

 

cal에서는 순서대로 앞에서 계산하기 때문에 덱으로 그냥 계산했다!

 

소스코드

#include <iostream>
#include <string>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
#define ll long long
int n;
ll ans = -1e18;
string arr;
vector<int> vt;
ll cal(deque<ll>& dq, deque<char>& op){
    while(!op.empty()){
        ll a = dq.front(); dq.pop_front();
        ll b = dq.front(); dq.pop_front();
        ll c = op.front(); op.pop_front();
        if(c=='+') a+=b;
        else if(c=='-') a-=b;
        else if(c=='*') a*=b;
        else a/=b;
        dq.push_front(a);
    }
    return dq.front();
}
ll solve(){
    deque<ll> dq;
    deque<char> op;
    int pos=0;
    for(int i=0;i<n;i++){
        if(pos<(int)vt.size() && vt[pos]==i){
            deque<ll> ddq;
            deque<char> oop;
            for(int j=vt[pos];j<=vt[pos+1];j++){
                if(j&1) oop.push_back(arr[j]);
                else ddq.push_back(arr[j]-'0');
            }
            dq.push_back(cal(ddq,oop));
            i=vt[pos+1]; pos+=2;
        }
        else{
            if(i&1) op.push_back(arr[i]);
            else dq.push_back(arr[i]-'0');
        }
    }
    return cal(dq,op);
}
 
int main(){
    scanf(" %d",&n);
    cin>>arr;
    int size = (n+1)/2;
    for(int i=0;i<(1<<size);i++){
        vt.clear();
        for(int j=0;j<size;j++){
            if(i&(1<<j)) vt.push_back(j*2);
        }
        if(vt.size()&1) continue;
        bool c = true;
        for(int j=0;j<(int)vt.size()-1;j+=2){
            if(vt[j+1]-vt[j] != 2) c=false;
        }
        if(!c) continue;
        ans = max(ans,solve());
    }
    printf("%lld\n",ans);
}