[boj] 백준 16637 괄호 추가하기 (c++) - dfs, 브루트포스

[문제]

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

[풀이]

dfs를 이용해서 풀 수 있다.

괄호를 묶는 경우, 현재 idx와 idx+2 가 피연산자가 되고, idx+1이 연산자가 된다. 따라서 이들의 계산 값과 현재 값을 계산해준 결과를 curr에 담아 dfs를 호출하는데, 이때 idx는 idx+4가 된다.

괄호를 묶지 않는 경우의 idx는 idx+2가 되며 curr에는 현재 idx와 이전 curr을 계산한 결과를 넘겨준다. 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#define INF 987654321

using namespace std;

int n;
string s;
int ans = -987654321;

int calculate(int a, int b, char op){
    switch(op){
        case '+': a+=b; break;
        case '-': a-=b; break;
        case '*': a*=b; break;
    }
    return a;
}

void dfs(int idx, int curr){
    //종료 조건
    if(idx>=n){
        ans = max(ans, curr);
        return;
    }

    char op = idx == 0 ? '+' : s[idx-1];

    //괄호를 묶는 경우
    if(idx+2 < n){
        int temp = calculate(s[idx]-'0', s[idx+2]-'0', s[idx+1]);
        dfs(idx+4, calculate(curr, temp, op));
    }

    //괄호를 안묶는 경우
    dfs(idx+2, calculate(curr, s[idx]-'0', op));

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //괄호를 적절히 추가해 얻을 수 있는 식의 최대값
    cin >> n >> s;

    dfs(0, 0);

    cout << ans;
}