[프로그래머스/Java] Lv.4 - 사칙연산

승래·2026년 3월 24일

프로그래머스 Lv.4 - 사칙연산

요구사항

숫자와 +, - 연산자로 이루어진 수식이 주어질 때
연산 순서를 마음대로 정해서 만들 수 있는 최댓값을 구하는 문제

접근 방식

구간 DP 로 풀었다.

구간 DP를 떠올리는 시그널

"연산 순서에 따라 결과가 달라진다"
"전체를 어떤 기준으로 나눌 수 있다"
→ 구간 DP 의심!

핵심 아이디어

숫자 인덱스: 0  1  2  3
             1  2  3  4
연산자:        +  -  +

dp[i][j] = i번째 숫자부터 j번째 숫자까지의 부분식

k를 기준으로 왼쪽/오른쪽으로 분할:
dp[0][2] = "1+2-3"
  k=0: (1) + (2-3)
  k=1: (1+2) - (3)
→ 모든 k를 시도해서 최대/최솟값을 구함

왜 최솟값도 관리해야 하는가?

- 연산에서:
  최댓값 = 왼쪽max - 오른쪽min
  최솟값 = 왼쪽min - 오른쪽max

→ 오른쪽이 음수(최솟값)일 때 빼면 더 커짐
→ 나중에 - 연산에 활용하기 위해 최솟값도 필요

점화식

+ 연산:
  maxDp[i][j] = max(leftMax + rightMax)
  minDp[i][j] = min(leftMin + rightMin)

- 연산:
  maxDp[i][j] = max(leftMax - rightMin)
  minDp[i][j] = min(leftMin - rightMax)

코드

import java.util.*;

class Solution {
    public int solution(String[] arr) {
        int n = arr.length / 2 + 1;
        ArrayList<Integer> num = new ArrayList<>();
        int[][] maxDp = new int[n][n];
        int[][] minDp = new int[n][n];

        for (int i = 0; i < arr.length; i += 2) {
            num.add(Integer.parseInt(arr[i]));
        }

        for (int i = 0; i < n; i++) {
            maxDp[i][i] = num.get(i);
            minDp[i][i] = num.get(i);
        }

        for (int len = 1; len < n; len++) {
            for (int i = 0; i < n - len; i++) {
                int j = i + len;
                maxDp[i][j] = Integer.MIN_VALUE;
                minDp[i][j] = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) {
                    String op = arr[k * 2 + 1];
                    int leftMax = maxDp[i][k], leftMin = minDp[i][k];
                    int rightMax = maxDp[k+1][j], rightMin = minDp[k+1][j];

                    if (op.equals("+")) {
                        maxDp[i][j] = Math.max(maxDp[i][j], leftMax + rightMax);
                        minDp[i][j] = Math.min(minDp[i][j], leftMin + rightMin);
                    } else {
                        maxDp[i][j] = Math.max(maxDp[i][j], leftMax - rightMin);
                        minDp[i][j] = Math.min(minDp[i][j], leftMin - rightMax);
                    }
                }
            }
        }

        return maxDp[0][n-1];
    }
}