(Elice / 브루트포스 / C++) 조교님, 점수 올려주세요

조교님, 점수 올려주세요

코더 대학교에서는 학생들의 점수를 수식으로 표기합니다. 수식은 0 이상, 9 이하의 정수와 연산자(+, -, x)로 이루어져 있습니다. 여기서 기존의 연산자의 우선순위는 무시하고, 무조건 왼쪽부터 순서대로 계산합니다. 예를 들어 4+3x2-5x3의 결과는 27입니다.

학생들의 점수를 매기는 조교인 체셔는 골치가 아픕니다. 왜냐하면 학기가 끝날 때 쯤이면 점수를 올려달라는 학생들이 찾아오기 때문입니다. 한 학생의 요청이 너무 간절하여 체셔는 학생의 수식에 괄호를 추가할 기회를 주었습니다.

학생의 점수 수식에 괄호를 추가하면 괄호 안에 들어 있는 식은 먼저 계산하게 됩니다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 합니다.

예를 들어, 4+3x2-5x3식에 4+(3x2)-(5x3)과 같이 괄호를 추가했으면, 식의 결과가 -5로 바뀌게 됩니다. 하지만, 4+((3x2)-(5x3)), (4+(3x2))-(5x3)처럼 괄호 안에 괄호가 들어가는 것은 허용하지 않습니다.

학생의 수식이 주어졌을 때, 괄호를 적절하게 추가하여 학생이 최고 점수를 받을 수 있도록 프로그램을 작성하세요.
(단, 추가하는 괄호의 개수 제한은 없으며, 추가하지 않아도 됩니다.)

 

지시사항

입력

• 첫째 줄에 수식의 길이를 나타내는 홀수 N을 입력합니다.

                                     (1≤N≤19)

• 둘째 줄에는 수식을 입력합니다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같습니다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아 가면서 나옵니다.
• 연산자는 +, -, * 중 하나입니다.

출력

• 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력합니다.

입력 예시

5
8*3+5

출력 예시

64

8 * (3 + 5)로 수정하면 최고 점수를 받을 수 있습니다.

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#define ll long long 
using namespace std;
int n;
ll maxval = LLONG_MIN;
vector<int> num;
vector<char> oper;
ll calculator(ll p1, ll p2, char operation) {
    switch (operation) {
    case '+':
        return p1 + p2;
    case '*':
        return p1 * p2;
    case '-':
        return p1 - p2;
    }
}

void solution(ll val, int cnt) {
    if (cnt == n / 2) {
        if (val > maxval)
            maxval = val;
        return;
    }
    ll val2 = calculator(val, num[cnt + 1], oper[cnt]);
    solution(val2, cnt + 1);
    if (cnt + 2 <= n / 2) {
        val2 = calculator(num[cnt + 1], num[cnt + 2], oper[cnt + 1]);
        val2 = calculator(val, val2, oper[cnt]);
        solution(val2, cnt + 2);
    }
}

int main() {
    char c;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> c;
        if (c >= '0' && c <= '9')
            num.push_back(c-'0');
        else
            oper.push_back(c);
    }
    solution(num[0], 0);
    cout << maxval << '\n';

    return 0;
}