[프로그래머스] 사칙연산 (분할 정복 + DP)

문제 소개

풀었던 프로그래머스 - 사칙연산 문제를 정리합니다.

이 문제는 사칙 연산(+, -) 순서에 따라 결과가 달라지는 연산식에서 최댓값을 구하는 문제입니다.

문제의 핵심은 괄호를 어떻게 치느냐에 따라 결과가 달라지기에 단순히 왼쪽부터 계산하는 게 아니라 모든 가능한 괄호 조합 (= 연산 순서) 을 탐색해야 합니다.

문제 링크: 사칙연산 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 모든 가능한 괄호 순서대로 계산하고 최댓값을 저장
   각 구간을 쪼개서 괄호를 다르게 결정 = 분할 정복으로 연산 결과 저장
2. 최댓값을 구하려면 한 연산자를기준으로 좌우 결과의 최소/최대가 저장되어야함
   • + 연산자 : 최댓값 + 최댓값 = 최대
   • -  연산자 : 최댓값 - 최솟값 = 최대
3. 각 구간의 최댓값과 최솟값을 모두 저장하면서 DP를 활용해 중복 계산 제거

---

해결 과정 및 코드

핵심 아이디어

1. 둘 다 전체 수식을 하나의 연산자로 분할 → 좌/우 부분을 재귀로 계산
2. arr[i ~ j] 범위에서,
   연산자 arr[k] (k는 홀수)에 대해 좌우를 나눕니다:
   • 왼쪽: arr[i ~ k-1]
   • 오른쪽: arr[k+1 ~ j]
                   [1 - 3 + 5 - 8] = f(0, 6)
                   /               |                \
       (1)-(3+5-8)   (1-3)+(5-8)   (1-3+5)-(8)=f(1, 4)+f(6, 6)
                /    ...
         (3)+(5-8) = f(2,2)+f(4, 6)
             /     ... 
          (5)-(8) = f(4, 4)+f(6, 6)
         /    ...
     (5) = f(4, 4)
3. 해당 연산자에 따라 좌/우 값들을 연산합니다
   • + 최댓값 + 최댓값 (최댓값), 최솟값 + 최솟값 (최솟값)
   • - 최댓값 - 최솟값 (최댓값), 최솟값 - 최댓값 (최솟값)

코드

시간 복잡도 : O(N³)
: N(≤201)의 숫자에 대해 구간 (i, j)마다 연산자를 중심으로 분할하며, 각각 getMax / getMin 함수가 재귀적으로 호출

import java.util.*;

class Solution {
    static Integer[][] dpMax, dpMin; // 최대값, 최소값 저장용
    static String [] gArr;
    public int solution(String arr[]) {
        int n = arr.length;
        gArr = arr;
        dpMax = new Integer[n][n];
        dpMin = new Integer[n][n];
        return getMax(0, n - 1); // 전체 범위의 최대값 반환
    }
    
    private int getMax(int start, int end) {
        // 분할 범위 Key 조회
        // start == end 일 경우 해당 인덱스 숫자
        if (dpMax[start][end] != null) return dpMax[start][end];
        if (start == end) return dpMax[start][end] = Integer.parseInt(gArr[start]);

        // start ~ end idx 범위에서 최대 연산 결과 계산
        int max = Integer.MIN_VALUE;
        for (int op = start + 1; op < end; op += 2) {
            int leftMax = getMax(start, op - 1);
            int rightMax = getMax(op + 1, end);
            int rightMin = getMin(op + 1, end);

            int result = gArr[op].equals("+")
                ? leftMax + rightMax
                : leftMax - rightMin;

            max = Math.max(max, result);
        }
        return dpMax[start][end] = max;
    }
    
    private int getMin(int start, int end) {
        // 분할 범위 Key 조회
        // start == end 일 경우 해당 인덱스 숫자
        if (dpMin[start][end] != null) return dpMin[start][end];
        if (start == end) return dpMin[start][end] = Integer.parseInt(gArr[start]);

        // start ~ end idx 범위에서 최소 연산 결과 계산
        int min = Integer.MAX_VALUE;
        for (int op = start + 1; op < end; op += 2) {
            int leftMin = getMin(start, op - 1);
            int rightMin = getMin(op + 1, end);
            int rightMax = getMax(op + 1, end);

            int result = gArr[op].equals("+")
                ? leftMin + rightMin
                : leftMin - rightMax;

            min = Math.min(min, result);
        }
        return dpMin[start][end] = min;
    }
}