괄호 추가하기

백준 16637번: 괄호 추가하기

아이디어

그냥 구현하면 됨.
괄호 사이에 연산자 하나밖에 못들어가니까 주의.
재귀로 잘 짜서 모든 경우의 수 미리 만들어놓고, 문자열 읽으면서 앞에서부터 계산하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
string S;
vector<string> v;

void make(string s, int idx, int open) {
    if (idx >= N) {
        if (!open) v.push_back(s);
        return;
    }
    if (!open) {
        make(s+'('+S[idx]+S[idx+1], idx+2, 1);
        make(s+S[idx]+S[idx+1], idx+2, open);
    }
    else {
        make(s+S[idx]+')'+S[idx+1], idx+2, 0);
    }
}

int cal (string& s) {
    int ret = 1;
    char op = '*';

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            string sub = "";
            i++;
            while (s[i] != ')') {
                sub += s[i];
                i++;
            }
            int val = cal(sub);
            if (op == '+') {
                ret += val;
            }
            else if (op == '-') {
                ret -= val;
            }
            else if (op == '*') {
                ret *= val;
            }
        }
        else if ('0' <= s[i] && s[i] <= '9') {
            if (op == '+') {
                ret += s[i]-'0';
            }
            else if (op == '-') {
                ret -= s[i]-'0';
            }
            else if (op == '*') {
                ret *= s[i]-'0';
            }
        }
        else {
            op = s[i];
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> S;
    make("", 0, 0);
    int m = INT_MIN;
    for (auto& s : v) {
        // cout << s << '\n';
        // cout << cal(s) << '\n';
        m = max(m, cal(s));
    }
    cout << m;

    return 0;
}

여담

문자열 공포증