BOJ 16638 - 괄호 추가하기 2

문제

• 아래 조건들을 만족하는 수식이 주어진다.
  • 길이가 1이상 19 이하
  • 수식의 수들은 모두 한 자릿수(0-9)
  • 연산자는 +, -, *
  • 연산자 우선순위 존재
  • 괄호 없음
• 아래 조건을 만족하며 수식에 괄호를 추가할 수 있을 때 결과의 최댓값을 출력해야 한다.
  • 괄호는 하나의 연산자만 포함 가능
  • 중복된 괄호 불가
• 입력은 올바른 수식만 주어진다.
• 정답은 \(-2^{31}\) 초과 \(2^{31}\) 미만이다.

풀이

• 괄호를 추가할 연산자를 비트마스크로 선택하고, 후위 표기법으로 바꾼 후 계산했다.
• 연산자가 최대 9개이기 때문에, 시간복잡도는 \(\text{O(} 2^{9} \times \text{N)}\)으로, 시간 제한인 0.5초를 초과하지 않는다.

코드

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using vi = vector<int>;

int pow(int x, int p) {
    int r = 1;
    while (p) {
        if (p & 0x01) r *= x;
        x *= x;
        p >>= 1;
    }
    return r;
}

bool isdigit(char c) {
    if (c >= '0' && c <= '9')
        return true;
    else
        return false;
}

string gen(string s, int msk, int n) {
    int idx = 0;
    vi wrap(n, 0);
    string res = "";
    for (int i = 0; i < n; i++) {
        wrap[i] = msk & 0x01;
        msk >>= 1;
    }
    for (int i = 1; i < n; i++) {
        if (wrap[i - 1] == 1 && wrap[i] == 1) return "";
    }
    for (int i = 0; i < s.length(); i++) {
        if (isdigit(s[i]))
            res.push_back(s[i]);
        else {
            if (wrap[idx]) {
                res.insert(res.end() - 1, '(');
                res.push_back(s[i]);
                res.push_back(s[i + 1]);
                res.push_back(')');
                i++;
            } else
                res.push_back(s[i]);
            idx++;
        }
    }
    return res;
}

int getp(char c) {
    if (c == '(')
        return 0;
    else if (c == '+' || c == '-')
        return 1;
    else if (c == '*')
        return 2;
    else
        return 3;
}

string trans(string s) {
    int n = s.length();
    string res = "";
    stack<char> op;
    for (int i = 0; i < n; i++) {
        if (isdigit(s[i]))
            res.push_back(s[i]);
        else if (s[i] == '(')
            op.push(s[i]);
        else if (s[i] == ')') {
            while (op.top() != '(') {
                res.push_back(op.top());
                op.pop();
            }
            op.pop();
        } else {
            int cp = getp(s[i]);
            if (op.empty() || getp(op.top()) < cp) {
                op.push(s[i]);
            } else {
                while (!op.empty() && getp(op.top()) >= cp) {
                    res.push_back(op.top());
                    op.pop();
                }
                op.push(s[i]);
            }
        }
    }
    while (!op.empty()) {
        res.push_back(op.top());
        op.pop();
    }
    return res;
}

int calc(string s) {
    int n = s.length();
    stack<long long> st;
    for (int i = 0; i < n; i++) {
        if (isdigit(s[i])) {
            st.push(s[i] - '0');
        } else {
            long long n1, n2;
            n2 = st.top();
            st.pop();
            n1 = st.top();
            st.pop();
            if (s[i] == '+')
                st.push(n1 + n2);
            else if (s[i] == '-')
                st.push(n1 - n2);
            else
                st.push(n1 * n2);
        }
    }
    return (int)st.top();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, pn, ans = -1 * pow(2, 31);
    string s;
    cin >> n;
    cin >> s;
    pn = pow(2, n / 2);
    for (int i = 0; i < pn; i++) {
        string ts = gen(s, i, n / 2);
        if (ts == "")
            continue;
        else {
            int t = calc(trans(ts));
            if (ans < t) ans = t;
        }
    }
    cout << ans;
    return 0;
}

풀고나서

• 괄호 추가하기 1을 제대로 읽지 않고 연산자 우선순위를 적용하고 풀다가 틀렸었다.
  2가 있어서 다행이었다.
• 연관 문제인 괄호 추가하기 3은 중복 괄호, 여러 연산자를 포함하는 괄호가 허용되는 문제로, 다음에 풀어볼 예정이다.
• 다른 사람들의 풀이를 보니 DFS로 푼 사람도 있었다.
  • 임의로 괄호를 추가할 수 있기 때문에 구현이 더 간단할 것 같다.
  • 괄호 추가하기 3은 simulation, 그래프 탐색 두 가지 방법으로 풀어봐야겠다.