[BOJ 16639] 괄호 추가하기3

백준 문제 링크

🔍 문제 분석

분석

• 수식을 최대로 만드는 괄호를 찾기 위해 완전탐색을 실시한다. 이 때, 동적계획법을 활용하여 시간 복잡도를 낮출 수 있다.
• 주의해야 할 점은 -연산과 *연산의 경우이다.
  • -연산의 결과가 최대가 되기 위해서는 좌변이 최대가 되고, 우변이 최소가 되어야 한다
  • *연산의 경우 좌변 및 우변이 음수가 되는 경우를 주의해야 한다.
• 위 연산들을 고려하기 위해 최댓값을 계산하는 함수와 최솟값을 계산하는 함수를 별도로 정의하고 상호 재귀(mutual recursion) 형태로 문제를 풀이한다.

💻 코드 구현

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX = 19;
constexpr ll INF = numeric_limits<ll>::max();
constexpr ll NEGINF = numeric_limits<ll>::min();

ll cache_max[MAX][MAX], cache_min[MAX][MAX];

bool is_digit(string s, int l, int r) {
    for (int i = l; i <= r; ++i) {
        if (!isdigit(s[i])) {
            return false;
        }
    }
    return true;
}

ll solve_min(string s, int l, int r);
ll solve_max(string s, int l, int r);

ll solve_max(string s, int l, int r) {
    if (is_digit(s, l, r)) return stoll(s.substr(l, r - l + 1));
    ll& ret = cache_max[l][r];
    if (ret != NEGINF) return ret;
    for (int i = l; i <= r; ++i) {
        if (isdigit(s[i])) continue;
        char op = s[i];
        switch (op) {
            case '+':
                ret = max(ret, solve_max(s, l, i - 1) + solve_max(s, i + 1, r));
                break;
            case '-':
                ret = max(ret, solve_max(s, l, i - 1) - solve_min(s, i + 1, r));
                break;
            case '*':
                ret = max(ret, solve_max(s, l, i - 1) * solve_max(s, i + 1, r));
                ret = max(ret, solve_min(s, l, i - 1) * solve_min(s, i + 1, r));
                ret = max(ret, solve_max(s, l, i - 1) * solve_min(s, i + 1, r));
                ret = max(ret, solve_min(s, l, i - 1) * solve_max(s, i + 1, r));
                break;
            default:
                assert(false && "Failed to parse an operator");
        }
    }
    return ret;
}

ll solve_min(string s, int l, int r) {
    if (is_digit(s, l, r)) return stoll(s.substr(l, r - l + 1));
    ll& ret = cache_min[l][r];
    if (ret != INF) return ret;
    for (int i = l; i <= r; ++i) {
        if (isdigit(s[i])) continue;
        char op = s[i];
        switch (op) {
            case '+':
                ret = min(ret, solve_min(s, l, i - 1) + solve_min(s, i + 1, r));
                break;
            case '-':
                ret = min(ret, solve_min(s, l, i - 1) - solve_max(s, i + 1, r));
                break;
            case '*':
                ret = min(ret, solve_max(s, l, i - 1) * solve_max(s, i + 1, r));
                ret = min(ret, solve_min(s, l, i - 1) * solve_min(s, i + 1, r));
                ret = min(ret, solve_max(s, l, i - 1) * solve_min(s, i + 1, r));
                ret = min(ret, solve_min(s, l, i - 1) * solve_max(s, i + 1, r));
                break;
            default:
                assert(false && "Failed to parse an operator");
        }
    }
    return ret;
}

int main() {
    fastio;

    fill(&cache_max[0][0], &cache_max[0][0] + MAX * MAX, NEGINF);
    fill(&cache_min[0][0], &cache_min[0][0] + MAX * MAX, INF);

    int n;
    string s;
    cin >> n >> s;
    cout << solve_max(s, 0, s.size() - 1);
}

📝 코드 설명

🔧 트러블 슈팅

📚 참고자료