3주차-6 16637번: 괄호 추가하기

- 주어지는 수에 괄호를 쳐서 가장 높은 수를 제출하는 문제

- 모든 경우의수를 체크해봐야 하므로 dfs를 사용한다!

- 이 문제의 경우 숫자와 기호를 다른 컨테이너로 분리하고, 인덱스를 통해 계산 순서를 변경하여 처리했다.

 

#include <bits/stdc++.h>

using namespace std;

vector<int> num_v;
vector<char> oper_v;

int n, ret = -987654321;
string s;

void fastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int oper(char a, int b, int c)
{
    if (a == '+') return b + c;
    if (a == '-') return b - c;
    if (a == '*') return b * c;
}

void go(int here, int _num)
{
    if (here == num_v.size() - 1)
    {
        ret = max(ret, _num);
        return;
    }
    
    go(here + 1, oper(oper_v[here], _num, num_v[here + 1]));
    
    if (here + 2 <= num_v.size() - 1)
    {
        int temp = oper(oper_v[here+1], num_v[here+1], num_v[here + 2]);
        go(here + 2, oper(oper_v[here], _num, temp));
    }
}

int main()
{
    fastIO();
    cin >> n;
    cin >> s;
    
    for (int i = 0; i < n; ++i)
    {
        if (i % 2 == 0) num_v.push_back(s[i] - '0');
        else oper_v.push_back(s[i]);
    }
    
    go(0, num_v[0]);
    cout << ret << endl;
    
    return 0;
    
}