[백준 16637] 괄호 추가하기

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

문제 조건 잘못 보고 조금 해맨 문제.

문제 분류

• 브루트포스
• 비트마스크

문제 해결 아이디어

문제의 조건은

1. 수식의 길이가 N (N ≤ 19, 홀수)
2. 숫자는 한자리로 구성됨.
3. 괄호는 중첩될 수 없음.
4. 괄호 안에는 연산자가 하나만 들어 있어야 함.

4번 문제 조건을 생각 안해서 좀 해맸다.

문제 해결 아이디어는 괄호에 넣을 연산자를 고르는 것이다.

연산자의 총 갯수는 N/2이고 N은 19이므로 괄호에 넣을 연산자와 괄호에 안 넣을 연산자를 구분해서 생각한다면 모든 케이스를 비트마스크 연산으로 손쉽게 순회할 수 있다.

예를 들면 이런 식인데

 

문제에 주어진 예제 입력 3에서

처음 *와 마지막 +는 괄호에 넣지 않는 연산자.

그 다음 +는 괄호에 넣는 연산자.

이렇게 구분하면 최대값을 구할 수 있다.

그러면 괄호에 넣는 연산자를 1이라고 표현할 때, 이러한 케이스는 010으로 표현할 수 있다.

이제 모든 케이스를 순회할 수 있으니 구현만 남았다.

구현

구현이 조금 까탈스러운데

calc 함수는 expression 문자열로부터 [start, end) 범위의 식을 계산한다.

예를 들면 "7+8-9"라는 문자열로 부터 숫자를 반환하는 식.

calc 함수를 사용하면 괄호로 묶은 수식을 계산할 수 있다.

괄호에 넣지 않는 숫자들도 이와같은 매커니즘으로 구하는데, 다만 연산에 들어갈 숫자들이 calc함수를 통해서 나와야한다.

 

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef long long ll;

int calc(string exp, int start, int end) {
    if (start + 1 == end) return exp[start] - '0';

    int ret = exp[start] - '0';
    for (int i = start + 1; i < end; i += 2) {
        char op = exp[i];
        int next = exp[i + 1] - '0';
        if (op == '+') {
            ret += next;
        } else if (op == '-') {
            ret -= next;
        } else {
            ret *= next;
        }
    }
    return ret;
}

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

    int N;
    string exp;
    cin >> N >> exp;
    int numop = N / 2;

    ll ans = -1e11;
    for (int i = 0; i < (1 << numop); i++) {
        vi ops;
        int last = -1;
        bool ok = true;
        for (int j = 0; j < numop; j++) {
            if (i & (1 << j)) {
                ops.push_back(2 * j + 1);
            } else {
                // 괄호 안의 연산이 2개 이상 나오면 무시하자.
                if (last != -1) {
                    if (last + 1 == j) {
                        ok = false;
                    }
                }
                last = j;
            }
        }
        if (!ops.empty() && !ok) continue;


        // 마지막 ops는 계산의 편의를 위해서 넣어준다.
        ops.push_back(N);
        ll ret = calc(exp, 0, ops[0]);
        for (int j = 0; j < ops.size() - 1; j++) {
            int curop = ops[j];
            int nextop = ops[j + 1];

            char op = exp[curop];
            int next = calc(exp, curop + 1, nextop);
            if (op == '+') {
                ret += next;
            } else if (op == '-') {
                ret -= next;
            } else if (op == '*') {
                ret *= next;
            } else {
                assert(false);
            }
        }

        ans = max(ans, ret);
    }

    cout << ans << endl;


    return 0;
}