Programmers 1843: 사칙연산

문제 조건

• 사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않는다
• 짝수번째는 숫자, 홀수번째는 연산자이다
• 문자열 형태의 숫자와, +, - 가 들어있는 배열의 계산 결과 중 최댓값을 구하는 문제이다

 

모든 경우에 대해 구하되, 구한 값을 어딘가 저장해 두어야 한다. => dp

dp[i][j]: 인덱스 i ~ j 까지 괄호 계산을 한 값이라고 정의하자.

이때, 양수 연산의 경우 뒤에 있는 값이 최대한 커야하고, 음수 연산의 경우 뒤에 있는 값이 최대한 작아야 최댓값을 구할 수 있다.

따라서 양수 연산이 앞에 있을 땐 dp에 최댓값을, 음수 연산이 앞에 있을 땐 dp에 최솟값을 저장하도록 한다.

 

class Solution {
	public int solution(String arr[]) {
		int n = arr.length;
		int[][] 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 calculateItoJ(arr, dp, 0, n - 1);
	}

	public static int calculateItoJ(String[] arr, int[][] dp, int i, int j) { // i부터 j까지 연산
		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) {
				int subResult = calculate(calculateItoJ(arr, dp, i, k), arr[k + 1], calculateItoJ(arr, dp, k + 2, j));
				result = Math.min(result, subResult);
			}
			dp[i][j] = result;

		} else { // + 연산 처리: 뒷부분이 최대가 되어야
			int result = Integer.MIN_VALUE;

			for (int k = i; k < j; k += 2) {
				int subResult = calculate(calculateItoJ(arr, dp, i, k), arr[k + 1], calculateItoJ(arr, dp, k + 2, j));
				result = Math.max(result, subResult);
			}
			dp[i][j] = result;

		}
		return dp[i][j];
	}

	public static int calculate(int a, String op, int b) {
		if (op.equals("-")) {
			return a - b;
		}
		if (op.equals("+")) {
			return a + b;
		}
		return 0;
	}
}