[백준 16637] 괄호 추가하기 (C++)

16637번: 괄호 추가하기

 

 

꿀 조건 1. 괄호 안에는 연산자 하나만 들어갈 수 있다.

꿀 조건 2. 중첩된 괄호는 사용할 수 없고, 항상 올바른 수식만 주어진다.

 

모든 괄호 안에는 정직하게 정수1, 연산자, 정수2 의 형태로 구성되어있다.

 

이 점을 활용해서 백트래킹을 사용한 브루트 포스로 현재 연산자를 둘러싸는 괄호를 추가하는 경우, 그냥 넘어가는 경우 모두에 대해서 수식의 값을 확인하면 답을 구할 수 있다.

 

현재 연산자가 괄호로 둘러싸일 경우, 바로 다음 연산자(현재인덱스+2)는 괄호를 사용할 수 없으며, 위치가 현재인덱스+4 인 연산자부터 괄호를 사용할 수 있으므로 시간복잡도를 확연히 낮출 수 있다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>

typedef long long ll;
// typedef pair<int, int> pii;

using namespace std;

int N;
string form;
int bracketOpen[22]; // 1은 open, -1은 close
int answer = -pow(2, 31);

void input(){
    cin >> N;
    cin >> form;
}

int calc(int p, int q, char op){
    int ret;
    
    switch (op){
        case '+': ret = p + q; break;
        case '*': ret = p * q; break;
        case '-': ret = p - q; break;
        default: break;
    }
    return ret;
}

int calcForm(){
    
    int left = form[0]-'0';
    
    for(int i = 1; i < N; i+=2){
        int now = form[i+1]-'0';
        if(bracketOpen[i]){
            left = calc(form[i-1]-'0', form[i+1]-'0', form[i]);
        }
        else if(bracketOpen[i+2]){
            left = calc(left, calc(form[i+1]-'0', form[i+3]-'0', form[i+2]), form[i]);
            i += 2;
        }
        else{
            left = calc(left, now, form[i]);
        }
    }
    
    return left;
}

void bruteForce(int now){
    if(now >= form.size()){
        answer = max(answer, calcForm());
        return;
    }
    
    bruteForce(now+2);
    
    // open&close bracket
    // 연산자 기준
    if(now % 2 == 1){
        bracketOpen[now] = 1;
        bruteForce(now+4);
        bracketOpen[now] = 0;
    }
}

void solve(){
    bruteForce(1);
    cout << answer;
}

int main(){
    input();
    solve();
    
    return 0;
}