프로그래머스 - 사칙연산

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 사칙연산

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

풀이 : DP 알고리즘을 통해 i부터 j까지의 연산을 하였을 때 최대값을 배열에 입력한다. 이후 0 ~ 마지막까지의 연산을 하였을 때의 최대값을 구한다.

class Solution {
    static int [][] dp;
    public int solution(String arr[]) {
		int n = arr.length;
		dp = new int [n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = Integer.MIN_VALUE;
			}
			if(i%2 == 0) dp[i][i] = Integer.parseInt(arr[i]);
		}
        return solve(arr, 0, n-1);
    }
    
    private static int solve(String[] arr, int i, int j) { // i부터 n-1까지 연산
		if(dp[i][j] != Integer.MIN_VALUE) return dp[i][j];
		if(i-1 >= 1 && arr[i-1].equals("-")) { // - 연산 처리
			int result = Integer.MAX_VALUE;
			for (int k = i; k < j; k += 2) {
				if(arr[k+1].equals("-")) result = Math.min(result, solve(arr, i, k) - solve(arr, k+2, j));
				else result = Math.min(result, solve(arr, i, k) + solve(arr, k+2, j));
			}
			dp[i][j] = result;
		}else { // + 연산 처리
			int result = Integer.MIN_VALUE;
			for (int k = i; k < j; k += 2) {
				if(arr[k+1].equals("-")) result = Math.max(result, solve(arr, i, k) - solve(arr, k+2, j));
				else result = Math.max(result, solve(arr, i, k) + solve(arr, k+2, j));
			}
			dp[i][j] = result;
		}
		return dp[i][j];
	}
}