BOJ 16637 : 괄호 추가하기

풀이 요약

재귀

풀이 상세

1. 가령 3*8+5 를 예를 들어보자. 괄호가 쓰이는 경우는 (38)+5 나, 3(8+5) 이다. 후위식을 먼저 해주느냐, 전위식을 먼저 하냐이다.

2. 전위식은 인덱스를 따라 호출 해주면 되고, 후위식은 괄호부분을 먼저 계산한후, 이전까지의 계산 값을 같이 계산하면 된다.

#include <iostream>
#include <vector>

using namespace std;
int N, ans=-987654321;
vector<char> v;
vector<int> n;

void input() {
    string str;
    cin >> N >> str;
    for (int i = 0; i < N; i++) {
        if (str[i] == '-' || str[i] == '*' || str[i] == '+') v.push_back(str[i]);
        else n.push_back(str[i] - '0');
    }
}

int cal(int fr, char op, int back) {
    switch (op) {
        case '+' :
            return fr + back;
        case '-' :
            return fr - back;
        case '*' :
            return fr * back;
    }
}

void dfs(int idx, int num) {
    if (idx >= N / 2) {
        ans = max(ans, num);
        return;
    }

    dfs(idx + 1, cal(num, v[idx], n[idx + 1]));
    if (idx + 2 <= N / 2) dfs(idx + 2, cal(num, v[idx], cal(n[idx + 1], v[idx + 1], n[idx + 2])));
}

void output() {
    cout << ans;
}

int main() {
    input();
    dfs(0, n[0]);
    output();
}