(BOJ 16639 괄호 추가하기 3) 완전 탐색을 가장한 DP

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

 

괄호 추가하기 1, 2를 풀고 난 후 이 문제를 보고 난 생각은

'비슷하게 완전 탐색으로도 풀 수 있지 않을까?' 였다.

 

하지만, 자유롭게 괄호 설정이 가능하다는 점 (중첩 가능, 들어가는 연산자 개수 상관X) 때문에 경우의 수가 기하급수적으로 많아져서, 이전 문제들의 완전 탐색 방식의 풀이는 불가능하다.

 

결국 문제는 '중첩 괄호'를 어떻게 만드느냐인데, Divide-and-conquer로 쉽게 가능하다.

다음 예시를 보자.

위 식의 결과를 'Res'라는 변수에 저장한다고 하자

3+8*7-9*2 라는 식은, 중앙의 *를 기점으로 다시 두 식으로 나눌 수 있다.

두 식의 계산 결과를 중앙의 연산자로 다시 연산해주는 방식으로 divide-and-conquer가 가능하다.

이는 두 식에 괄호를 씌워 계산하는 것과 같다.

 

위 파란색 식의 결과를 Res라고 한다면, 이게 다른 식의 일부로 들어간다고 생각할 수 있다.

이때 res안의 괄호들은 괄호 안의 괄호, 즉 중첩 괄호가 되는 것이다.

 

 

 

k는 식을 둘로 쪼개는 중심점이 되는 중앙 연산자의 위치

 

i~j 범위로 표현되는 식을 k위치의 연산자 op를 기점으로 둘(front, back)로 쪼개자.

이렇게 쪼개면 분명 중복되는 요소가 생길 것이다 → memoization 활용 (DP인 이유)

 

dp(i,j) 답은 (front op back) 의 최댓값이다 (divide-and-conquer에서의 merge)

 

주의할 점은, 음수*음수 같은 경우도 양수가 되면서 최댓값이 될 수도 있기 때문에,

'최댓값 op 최댓값' 뿐만 아니라 '최솟값 op 최솟값' 같은 경우도 고려해줘야 한다.

(즉, max값 뿐만 아니라 min값도 트랙킹해야 한다는 소리)

 

 

i~j 식을 계산했을 때, min max 값을 저장하는 배열을 만들자.

min, max 값은 Divide했던 식의 결과를 합치는 과정에서 구할 수 있다.

 

Q. max op max, min op min 만 고려하면 되지 않나요?

max op min 이나 min op max는 왜?

> '부호의 마법'

front = {3, 5}, back = {-3, -1} 인 경우, min op max가 최댓값임 

 

 

Base condition은 dp(4,4) 같은 경우.

이땐 해당 숫자를 바로 반환해주면 된다.

Base condition

 

 

다른 사람들의 풀이를 보면 Bottom-up으로 구현한게 많은데, 솔직히 너무 이해하기 힘들었다.

어차피 점화식만 있으면 Top-down이든 Bottom-up이든 모두 가능해서, 난 top-down으로 짜봤다.

 

#include <limits.h> 
using ll = long long;
using pll = pair <ll, ll> ;
int N;
string s;
ll maxdp[20][20], mindp[20][20];

ll calc(ll a, ll b, char op) {
    switch (op) {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    }
}

// @Parameter i, j : expression range to calculate s[i...j]
// @Return pair<ll, ll> {minval, maxval} calculated in expression s[i...j]
pll dp(int i, int j) {
    if (i == j)
        return { s[i] - '0', s[i] - '0' };

    ll& maxval = maxdp[i][j];
    ll& minval = mindp[i][j];
    if (maxval != -1 && minval != -1) return {minval, maxval}; 
    // if maxdp is updated, mindp is updated as well

    maxval = LLONG_MIN;
    minval = LLONG_MAX;

    // s[k] = operator that separated s[i..j] into two parts (front, back)
    for (int k = i + 1; k < j; k += 2) {
        char ops = s[k];
        pll front = dp(i, k-1), back = dp(k+1, j);
        ll min1 = front.first, max1 = front.second, min2 = back.first, max2 = back.second;

        // 4 possible ways to calculate(= merge) 'front' and 'back'        
        vector<ll> calRes(4);
        calRes[0] = calc(max1, max2, ops);
        calRes[1] = calc(max1, min2, ops);
        calRes[2] = calc(min1, max2, ops);
        calRes[3] = calc(min1, min2, ops);
        sort(all(calRes));

        // Update current maxval, minval
        maxval = max(maxval, calRes[3]);
        minval = min(minval, calRes[0]);
    }

    return { minval, maxval };
}

int main() {
#ifdef DBG
    freopen("../input.txt", "r", stdin);
#endif
    fastio;

    cin >> N >> s;

    // Init
    memset(maxdp, -1, sizeof(maxdp));
    memset(mindp, -1, sizeof(mindp));
    FOR(i, 0, N) {
        if (!isdigit(s[i])) continue;
        maxdp[i][i] = s[i] - '0';
        mindp[i][i] = s[i] - '0';
    }

    pll res = dp(0, N-1);

    cout << maxdp[0][N-1] << "\n";
}

 

훨씬 더 직관적이고 깔끔하다.