🌞문제

🌞접근법

이 문제의 경우 arr의 영역을 통해서 dp 배열을 만들 수 있다.
dp 배열을 만드는 순서는 이렇다.

여기서 이 dp배열은 MAX[i][j], MIN[i][j]
두개의 dp 배열을 만들게 되고, 각각이 피연산자 i부터 j까지의 연산결과의 최댓값과 최솟값이 배열에 들어가게 된다.

이 dp 배열을 채우는 순서는 이렇다.
1. 피연산자가 하나만 있는 경우에 대한 결과
2. 피연산자가 두개 있는 경우
3. 피연산자가 세개 있는 경우
4. 피연산자가 n개 있는 경우

위와 같은 순서로 하는 이유는
예시로 피연산자가 세개 있다고 했을 때,
이에 대한 경우의 수는 이렇다.
1. 피연산자 1개와 피연산자 2개의 대한 결과값의 연산 (연산자 +, -)
2. 피연산자 2개의 대한 결과값의 연산과 피연산자 1개의 연산(연산자 +, -)

더불어 여기서 +와 -에 대해서 MAX가 들어가는지 MIN이 들어가는지가 달라지는데,
연산자가 -인 경우에는 A-B에서 A는 최댓값 B는 최솟값이 되어야 최댓값이 나올 것이다.
연산자가 +인 경우에는 A+B에서 A,B 모두 최댓값이 되어야 최댓값이 나올 것이다.

다시 dp배열을 채우는 순서 내용으로 돌아가서,
1번과 2번의 내용을 살펴보면 3개의 피연산자가 있는 경우의 dp배열을 채우기 위해서는
피연산자 1개 짜리와 피연산자 2개짜리의 결과값이 필요하다는 것을 알 수 있다.
그렇기 때문에 dp배열을 채우는 순서를 위와 같이 정의 할 수 있다.

🌞답

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

using namespace std;

int MAX[102][102];
int MIN[102][102];
int oper_count;

int solution(vector<string> arr)
{
    oper_count = arr.size() / 2 + 1 ;
    
    fill(&MAX[0][0], &MAX[101][101], -10000000);
    fill(&MIN[0][0], &MIN[101][101], 10000000);
    
    for(int i=0; i<oper_count ; i++)
    {
        MAX[i][i] = stoi(arr[i*2]);
        MIN[i][i] = stoi(arr[i*2]);
    }
    
    for(int count=1; count<oper_count ; count++) // 피연사자가 2개~n까지일때 까지의 for문
    {
        for(int i=0 ;i+count<oper_count;i++)//모든 i개의 경우 for문
        {
            int j=i+count;
            for(int k=i;k<j;k++)//모든 연산 가능의 방법에 대한 for문
            {
                if(arr[k*2+1] == "+")
                {
                    MAX[i][j] = max(MAX[i][j],MAX[i][k]+MAX[k+1][j]);
                    MIN[i][j] = min(MIN[i][j],MIN[i][k]+MIN[k+1][j]);
                }
                else
                {
                    MAX[i][j] = max(MAX[i][j],MAX[i][k]-MIN[k+1][j]);
                    MIN[i][j] = min(MIN[i][j],MIN[i][k]-MAX[k+1][j]);
                }
            }
        }
    }
    
    for(int i=0;i<oper_count;i++)
    {
        for(int j=0;j<oper_count;j++)
        {
            cout << MAX[i][j] <<" ";
        }
        cout<<endl;
    }
    
    int answer = MAX[0][oper_count-1];
    return answer;
}