[Programmers] 사칙연산

https://school.programmers.co.kr/learn/courses/30/lessons/1843?language=cpp

프로그래머스

 

 

1. Python

def solution(arr):
    N = len(arr) // 2 + 1
    INF = int(1e9)
    max_dp = [[-INF] * N for _ in range(N)]
    min_dp = [[INF] * N for _ in range(N)]
    for length in range(1, N+1):
        for i in range(N-length+1):
            if length == 1:
                max_dp[i][i] = int(arr[2*i])
                min_dp[i][i] = int(arr[2*i])
            else:
                j = i + length - 1
                for k in range(i, j):
                    opt = arr[2*k+1]
                    if opt == '+':
                        max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j])
                        min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j])
                    else:
                        max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j])
                        min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j])
    return max_dp[0][-1]

 

 

2. C++

#include <vector>
#include <string>
#include <climits>

using namespace std;

int solution(vector<string> arr)
{
    int N = arr.size() / 2 + 1;
	int max_dp[N][N];
	int min_dp[N][N];
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			max_dp[i][j] = -INT_MAX;
			min_dp[i][j] = INT_MAX;
		}
	}
	for (int length=1; length<=N; length++) {
		for (int i=0; i<N-length+1; i++) {
			if (length == 1) {
				max_dp[i][i] = stoi(arr[2*i]);
				min_dp[i][i] = stoi(arr[2*i]);
			}
			else {
				int j = i + length - 1;
				for (int k=i; k<j; k++) {
					string opt = arr[2*k+1];
					if (opt == "+") {
						max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j]);
						min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j]);
					} else {
						max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j]);
						min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j]);
					}
				}
			}
		}
	}
	return max_dp[0][N-1];
}