백준 16637번 괄호 추가하기 C++

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

 

괄호를 넣을 수 있는 가능한 모든 경우들을 검사하면서 가장 큰 값을 찾았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

#include <bitset>

using namespace std;
using int64 = long long;

int n;
string str;
vector<int> compBits;

enum Operator {
    Add,
    Sub,
    Mul,
};

map<char, Operator> oper;

int ans = INT_MIN;

void Solve(int bit, int cnt) {
    if (cnt >= n / 2 + 1) {
        int res = 0;
        Operator currOperator = Add;
        int idx = 0;

        while (true) {
            if (bit & compBits[idx]) {
                if (idx >= n / 2) return;

                int val = 0;
                int left = str[idx * 2] - '0';
                int right = str[idx * 2 + 2] - '0';
                Operator op = oper[str[idx * 2 + 1]];
                switch (op) {
                case Add:
                    val = left + right;
                    break;
                case Sub:
                    val = left - right;
                    break;
                case Mul:
                    val = left * right;
                    break;
                }

                switch (currOperator) {
                case Add:
                    res += val;
                    break;
                case Sub:
                    res -= val;
                    break;
                case Mul:
                    res *= val;
                    break;
                }
                if (idx + 2 > n / 2) break;
                if (idx * 2 + 3 < str.length())
                    currOperator = oper[str[idx * 2 + 3]];
                idx += 2;
            }
            else {
                int val = str[idx * 2] - '0';
                switch (currOperator) {
                case Add:
                    res += val;
                    break;
                case Sub:
                    res -= val;
                    break;
                case Mul:
                    res *= val;
                    break;
                }
                if (idx >= n / 2) break;
                currOperator = oper[str[idx * 2 + 1]];
                idx++;
            }
        }
        ans = max(ans, res);
        return;
    }
    if ((bit & 1) == 1) {
        Solve(bit << 1, cnt + 1);
    }
    else {
        Solve((bit << 1) | 1, cnt + 1);
        Solve(bit << 1, cnt + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    cin >> str;
    compBits = vector<int>(n / 2 + 1);
    int compBit = 1 << n / 2;
    for (int i = 0; i < compBits.size(); i++) {
        compBits[i] = compBit;
        compBit >>= 1;
    }
    oper.insert({ '+',Add });
    oper.insert({ '-',Sub });
    oper.insert({ '*',Mul });
    Solve(0, 0);
    cout << ans;
}