[프로그래머스] 사칙연산 c++

 

풀이

매번 괄호 안을 연산해주면 시간이 많이 걸리기 때문에 괄호안의 결과를 저장해서 계산해주었다.
dp를 이용해 풀었다.

연산이 더하기냐 뺴냐에 따라 최댓값을 만드는 방법이 달라진다.

+일때 : (최댓값)+(최댓값)

-일때 :(최솟값)-(최댓값)

그러므로 괄호안의 연산의 최솟값도 dp를 이용해 구해놓아야한다.

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<int>>dp_max(202,vector<int>(202,-10000000));
vector<vector<int>>dp_min(202,vector<int>(202,10000000));
vector<string> arr;

int calculate(int start, int end,int isMax){
    
    
    if(isMax & (dp_max[start][end] !=-10000000) )
        return dp_max[start][end];
    if(!isMax &(dp_min[start][end]!=10000000 ))
        return dp_min[start][end];
    if(start==end)
        return dp_max[start][end];
    
    for(int i=start+1;i<end;i+=2){
        if(arr[i]=="+"){
            dp_max[start][end] = max(dp_max[start][end],calculate(start,i-1,true) + calculate(i+1,end,true));
            dp_min[start][end] = min(dp_min[start][end],calculate(start,i-1,false) + calculate(i+1,end,false));
        }
        else if(arr[i]=="-"){
           
            dp_max[start][end] = max(dp_max[start][end],calculate(start,i-1,true) - calculate(i+1,end,false));
            dp_min[start][end] = min(dp_min[start][end],calculate(start,i-1,false) - calculate(i+1,end,true));
        }
            
    }
   if(isMax)
       return dp_max[start][end];
    else
        return dp_min[start][end];
}
int solution(vector<string> _arr)
{
    int answer=-1;
    arr=_arr;
    for(int i=0;i<arr.size();i+=2){
        dp_max[i][i] = stoi(arr[i]);
        dp_min[i][i] = stoi(arr[i]);
    }
    calculate(0,arr.size()-1,true);
    answer = dp_max[0][arr.size()-1];
   

    return answer;
}