16637번 괄호 추가하기

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

작년인가 풀려고 시도하였다가 시작도 거의 못 한 나에게는 어려운 문제였다.

그러다가 잠깐 시간이 남아서 풀었는데 신기하게도 풀렸다.

처음 풀 당시에는 길이 제한도 19밖에 안 됐었지만, 나올 수 있는 모든 경우의 수가 너무 많고, 무식한 방법인 것 같아서

시도조차 안 했다.

하지만, 길이가 19인 식을 직접 A4에 써보면서 나올 수 있는 모든 괄호의 경우의 수를 생각하고 써보니

별로 많지 않았다.

그래서 나올 수 있는 모든 경우의 수를 백트래킹 함수를 통해 구현하였다.

더 말하자면,

1+2+3+4+9*1+9

일 때,

각 연산자의 문자열 인덱스 번호는 1, 3, 5, 7, 9, 11임을 알 수 있다.

그래서 첨부한 코드 기준 66번 째 줄을 보면 이런 식으로 구현되어 있다.

참고로 23 ~ 27번 째 줄을 구현한 이유는

1+2+3..을 보자면

괄호는

(1+2)+3 이거나 1+(2+3)이다.

(1+(2)+3) 이런 식으로 묶을 수 없다.

즉, 연산자에 대한 문자열 인덱스의 번호는 서로 차이가 4이상이 되어야 한다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 20
 
int n, ans = INT32_MIN, temp[Max];
string s;
bool use[Max];
 
int calc(int a, int b, char c)
{
    if (c == '+') return a + b;
    if (c == '-') return a - b;
    if (c == '*') return a * b;
}
 
void bt(vector<int> vc, int idx)
{
    if (!vc.empty()) {
 
        // 차이가 2차이 나는 것은 안 된다.
        for (int i = 0; i < vc.size() - 1; i++) {
            if (vc[i + 1] - vc[i] == 2) {
                return;
            }
        }
 
        memset(use, false, sizeof(use));
 
        for (auto i : vc) {
            if (i == 1) {
                // 어차피 첫 번째 연산자는 괄호가 필요 없다.
                continue;
            }
            use[i] = true;
 
            // 미리 괄호 안에 있는 수식의 결과를 temp 배열에 저장한다.
            temp[i] = calc(s[i - 1] - '0', s[i + 1] - '0', s[i]);
        }
 
        // 첫 숫자
        int number = s[0] - '0';
 
        for (int i = 1; i < n - 1; i += 2) {
            if (i + 2 < n && use[i + 2]) {
                // i + 2가 범위를 벗어나지 않고, s[i + 2](=연산자)가 괄호 안에 있는 연산자라면 계산
                // 1*2+3이고 1*(2+3)을 계산한다고 하자.
                // 그렇다면 *(i=1)를 계산할 때 +(i+2)가 괄호 안에 있는 연산자라면 
                // 미리 계산된 결과(temp[i + 2])를 불러와야한다.
                number = calc(number, temp[i + 2], s[i]);
            }
            else {
                if (use[i]) {
                    // 괄호 안에 있는 연산자라면 아래의 식을 수행할 필요가 없다.
                    continue;
                }
                number = calc(number, s[i + 1] - '0', s[i]);
            }
        }
 
        ans = max(ans, number);
    }
 
    // 나올 수 있는 모든 괄호의 수(연산자가 기준이다.)
    for (int i = idx; i < n - 1; i += 2) {
        vc.push_back(i);
        bt(vc, i + 2);
        vc.pop_back();
    }
}
 
int main()
{
    cin.tie(0);
 
    cin >> n >> s;
 
    vector<int> v;
    bt(v, 1);
 
    if (n == 1) cout << s << "\n";
    else printf("%d\n", ans);
 
    return 0;
}