[BOJ] 16639 : 괄호 추가하기 3

문제 링크

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

16639번: 괄호 추가하기 3

주어진 식에 괄호를 추가해서 가장 큰 값을 만들어내는 문제.

풀이

DP를 이용해서 구간별로 가장 큰 값을 계속 구한다음 마지막에 1부터 N까지 범위에서 가장 큰 값을 출력해주면 된다.

수식에 들어가는 숫자는 0~9사이의 숫자이므로 음수는 식에 입력되지 않는다.

먼저 내가 했던 실수는 "가장 큰 값" 을 출력한다는 키워드에만 집중해서 구간별로 최대값만 계속 구하고 있었다. 대부분 예제는 잘 나왔지만 "-" 기호가 들어간 예제만 만나면 값이 이상하게 출력되었다.

+, -, * 기호별로 최대값이 나오는 상황을 생각해보자.

1. + : 최대값 + 최대값 = 최대값

2. - : 최대값 - 최소값 = 최대값

3. * : 양수 * 양수 또는 음수 * 음수 면 가장 크겠지만 여건이 안된다면 양수 * 음수를 해야하는 상황이 생긴다.

즉 , * 기호일때는 최대 * 최소, 최소 * 최대, 최대 * 최대, 최소 * 최소 모두 해보고 가장 큰 값을 찾아야 한다.

따라서 구간별로 "최소값"도 저장하고 있어야 최대값을 찾을 수 있다.

그래서 DP배열을 DP[최대 or 최소][구간 시작점][구간 끝점] 으로 설정해주었다.

DP[0][i][j] 는 i~j 구간의 최대값을 저장하고 DP[1][i][j] 는 i~j 구간의 최소값을 저장했다.

괄호를 씌우는 구간은 수식의 길이가 그렇게 길지 않기때문에 모든 경우를 다 고려해주었다.

만약 현재 탐색중인 구간이 1 + 3 * 5 - 4 라는 식이라고 하면 (1) + (3 * 5 - 4) , (1 + 3) * (5 - 4) , (1 + 3 * 5) -  (4) 이렇게 모든 경우를 고려해서 최대값과 최대값을 찾아준다. 여기서 (3 * 5 - 4) 또는 (1 + 3 * 5) 의 최대, 최소값은 이미 앞서 찾아놓았을 것이므로 가져와서 쓰면된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF_MAX = INT_MAX;
const int INF_MIN = INT_MIN;
const int MAX_N = 20;
int N;
int Num[MAX_N];
char Operator[MAX_N];
int DP[2][MAX_N][MAX_N];
int main(void)
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            DP[0][i][j] = INF_MIN;
            DP[1][i][j] = INF_MAX;
        }
    for (int i = 1; i <= N; i++) {
        if (i % 2 == 1)
            cin >> Num[(i + 1) / 2];
        else if (i % 2 == 0)
            cin >> Operator[i / 2];
    }
    for (int i = 1; i < (N + 1) / 2; i++) {
        if (Operator[i] == '-') {
            DP[0][i][i + 1] = Num[i] - Num[i + 1];
            DP[1][i][i + 1] = Num[i] - Num[i + 1];
        }
        else if (Operator[i] == '+') {
            DP[0][i][i + 1] = Num[i] + Num[i + 1];
            DP[1][i][i + 1] = Num[i] + Num[i + 1];
        }
        else if (Operator[i] == '*') {
            DP[0][i][i + 1] = Num[i] * Num[i + 1];
            DP[1][i][i + 1] = Num[i] * Num[i + 1];
        }
    }
    for (int i = 1; i <= N; i++)
        DP[0][i][i] = DP[1][i][i] = Num[i];
    for (int i = 2; i < (N + 1) / 2; i++) {
        for (int j = 1; j <= (N + 1) / 2 - i; j++) { // j ~ j + i 까지
            for (int t = 0; t < i; t++) { // t는 괄호를 씌울 구간을 정하는 경계선
                if (Operator[j + t] == '+') {
                    DP[0][j][j + i] = max(DP[0][j][j + i], DP[0][j][j + t] + DP[0][j + t + 1][j + i]);
                    DP[1][j][j + i] = min(DP[1][j][j + i], DP[1][j][j + t] + DP[1][j + t + 1][j + i]);
                }
                else if (Operator[j + t] == '-') {
                    DP[0][j][j + i] = max(DP[0][j][j + i], DP[0][j][j + t] - DP[1][j + t + 1][j + i]);
                    DP[1][j][j + i] = min(DP[1][j][j + i], DP[1][j][j + t] - DP[0][j + t + 1][j + i]);
                }
                else if (Operator[j + t] == '*') {
                    DP[0][j][j + i] = max(DP[0][j][j + i], max(DP[0][j][j + t] * DP[0][j + t + 1][j + i],
                        max(DP[0][j][j + t] * DP[1][j + t + 1][j + i], max(DP[1][j][j + t] * DP[1][j + t + 1][j + i], DP[1][j][j + t] * DP[0][j + t + 1][j + i]))));
 
                    DP[1][j][j + i] = min(DP[1][j][j + i], min(DP[0][j][j + t] * DP[0][j + t + 1][j + i],
                        min(DP[0][j][j + t] * DP[1][j + t + 1][j + i], min(DP[1][j][j + t] * DP[1][j + t + 1][j + i], DP[1][j][j + t] * DP[0][j + t + 1][j + i]))));
                }
            }
        }
    }
    cout << DP[0][1][(N + 1) / 2] << "\n";
    return 0;
}

이 문제를 대회나 코딩테스트에서 만났으면 못풀었거나 시간을 엄청 잡아먹었을 것 같다. 아직 DP는 어렵다.