괄호 추가하기3 (BOJ16639)

문제

이미지클릭

문제 설명

• 괄호를 개수에 상관없이 삽입하여서 식을 최대로 만들 수 있는 경우를 구하는 것이다.
• 숫자는 한 자리 숫자로 이루어져 있고, (+,-,*) 연산자가 있다.

3+8*7-9*2

• 식의 총길이는 19 보다 작다.

문제 해설

• dp

1. 연산
괄호의 연산중에서 곱하기에서 문제가 발생하였다.
(음수)*(음수)
음수끼리의 연산에서 최댓값이 발생할 수도 있기 때문에 dp배열을 최솟값과 최댓값을 각각 나누어서 시행해 주었다.
2. dp로직
구간 dp를 활용하여서 dp탐색을 해주었다. 
dp [시작][끝]: 시작~끝까지의 범위에서 최댓값과 최솟값을 저장해 주었다.

최종 코드

#include <bits/stdc++.h>
using namespace std;
int n;
long long mx_dp[24][24], mn_dp[24][24];
long long calculate(long long a, long long b, char op) { #연산
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    return 0;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    vector<int> num(n / 2 + 1);
    vector<char> sign(n / 2);
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) cin >> num[i / 2];
        else cin >> sign[i / 2];
    }
    for (int i = 0; i <= n / 2; i++) {
        mx_dp[i][i] = num[i];
        mn_dp[i][i] = num[i];
    }
    for (int len = 1; len <= n / 2; len++) {
        for (int i = 0; i + len <= n / 2; i++) {
            int j = i + len; #구간을 정하여서 i~j 범위의 최대 최소를 구해준다.
            mx_dp[i][j] = INT_MIN;
            mn_dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                long long mx1 = calculate(mx_dp[i][k], mx_dp[k + 1][j], sign[k]);
                long long mx2 = calculate(mx_dp[i][k], mn_dp[k + 1][j], sign[k]);
                long long mn1 = calculate(mn_dp[i][k], mx_dp[k + 1][j], sign[k]);
                long long mn2 = calculate(mn_dp[i][k], mn_dp[k + 1][j], sign[k]);
                #최대값*최대값, 최대값*최솟값, 최솟값*최댓값, 최솟값*최솟값
                mx_dp[i][j] = max({mx_dp[i][j], mx1, mx2, mn1, mn2});
                mn_dp[i][j] = min({mn_dp[i][j], mx1, mx2, mn1, mn2});
                #mn1,mn2,mx1,mx2중에 최대인지 알 수 없기 때문에 mx_dp,mn_dp에 4가지 연산 결과를 비교해야한다. 
            }
        }
    }
    cout << mx_dp[0][n / 2];
}

이미지클릭