사칙연산 C++

https://programmers.co.kr/learn/courses/30/lessons/1843

코딩테스트 연습 - 사칙연산

#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX = 205;
int dp[MAX][MAX][2]; //0:최솟값, 1:최댓값

void sol(vector<string> arr, int ii, int jj) {
	for (int k = ii + 1; k < jj; k += 2) {
		if(dp[ii][k-1][0] == 2e9) 	sol(arr, ii, k - 1);
		else if (dp[k + 1][jj][0] == 2e9) sol(arr, k + 1,jj);
		if (arr[k] == "-") {
			dp[ii][jj][0] = min(dp[ii][k - 1][0] - dp[k + 1][jj][1],dp[ii][jj][0]);
			dp[ii][jj][1] = max(dp[ii][k - 1][1] - dp[k + 1][jj][0],dp[ii][jj][1]);
		}
		else {
			dp[ii][jj][0] = min(dp[ii][k - 1][1] + dp[k + 1][jj][1],dp[ii][jj][0]);
			dp[ii][jj][1] = max(dp[ii][k - 1][1] + dp[k + 1][jj][1],dp[ii][jj][1]);
		}
	}
}

int solution(vector<string> arr)
{
	int answer = -1;
	for (int i = 0; i < arr.size(); i++) {
		for (int j = 0; j < arr.size(); j++) {
			dp[i][j][0] = 2e9;
			dp[i][j][1] = -2e9;
		}
	}

	for (int i = 0; i < arr.size(); i += 2) {
		dp[i][i][0] = stoi(arr[i]);
		dp[i][i][1] = stoi(arr[i]);
	}

	sol(arr, 0, arr.size()-1);

	answer = max(dp[0][arr.size()-1][0], dp[0][arr.size() - 1][1]);
	return answer;
}