프로그래머스 사칙연산 java

전수민

Nov 20, 2025

TABLE OF CONTENTS

(3) DFS를 쓰지만, DP의 재활용을 활용

1. 문제에 대하여 📦

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1843

연산식이 주어졌을 때, 괄호를 적절하게 쳐서 최대 결과를 만드는 문제.

(1) 조건 분석 📊

연산자와 피연산자의 위치는 옮길 수 없다.

2. 코드가 나오기까지 🛠️

KEY WORD: DP, DFS

(1) TOP-DOWN의 원리

주어진 모든 사칙연산의 마지막 연산은 다음과 같을 것이다. 최종 두개의 그룹으로 나눠지고 그것들을 더하거나, 빼서 ans가 최대값이 되도록 하는 것이다. 그렇다면, a와 b는 각각 무슨 값이 나와야 하는가?
a+b = ans 형태에서는 a,b 둘 다 최대값이 나와야 하고, a-b에서는 a가 최대값, b는 최소값이 나와야 결과가 나온다.

a와 b를 다시 나누면 a를 구하기 위한 최종 두개의 피연산자로 나뉘어질 것이고, b 또한 마찬가지일 것이다. 따라서 위와 같이 최종 연산에서 두개의 피연산자로 구체화하여 내려가는 TOP-DOWN 방식으로 풀 수 있다.

(2) 구해야할 경우의 수

위에서도 어떤 경우는 최대값을 구해야하고 어떤 경우는 최소값을 구해야 하고가 나뉘었다. 이 구해야할 경우의 수들을 생각해보고자 한다. 구해야할 경우의 수는 묶음의 외부 연산자에 의해 결정된다.

현재 가정은 원래 a+z = ans 라는 식에서 TOP-DOWN을 진행해서 b+c = z를 구하는 상황이라 해보자.

좌상단의 a + (b+c)의 경우 b,c 모두 최대값이 되어야 ans가 최대값이 될 것이다.

그 옆의 a + (b-c)의 경우는 b는 최대값, c = 최소값이 되어야 ans가 최대값이 될 것이다.

a-(b+c)는 b,c 모두 최소값이 되어야 ans의 최대값을 구할 수 있다.

a-(b-c)는 b는 최소값, c는 최대값이 되어야 ans의 최대값을 구할 수 있다.

b와 c 사이에 연산자는 정해져 있음으로 b (연산자) c 의 결과가 최대가 되는 경우의 수, 최소가 되는 경우의 수를 미리 구해놓고 필요할 때마다 꺼내 써야 한다.

(3) DFS를 쓰지만, DP의 재활용을 활용

3차원 배열을 만든다. 각 선의 쓰임새는 다음과 같다.


dp(구한 것이 최대값인지, 최소값인지)(연산 시작 위치)(연산 끝 위치)

1항은 연산의 결과가 최대값을 뜻하는지 최소값을 뜻하는지를 나타내고 2,3항은 현재 구하는 계산 식의 범위를 나타낸다.

(4) 시간복잡도 분석 ⏳

dfs가 가능한 이유는 숫자 압축떄문인 것 같다. 총 숫자는 101개이지만 a (연산자) b 꼴로 묶이면서 압축되기 때문에 실제 계산은 50 개 이하의 숫자를 대상으로 한다.

그 50개를 대상으로 dfs를 진행하여 3차원 배열을 채워나가므로 최종 시간복잡도는 다음과 같다.
$$
O(50^3)
$$

3. 코드 🌐

(1) SUDO CODE 💬


1. 초기화
2. dfs를 탄다. 각 깊이마다 a+b 혹은 a-b 형태를 띌테고 그때마다 필요한 최대값 혹은 최소값을 구해서 연산을 완성한다.
- dfs에서 중요한 점
  : 매번 새로운 계산을 하면 시간초과가 날 수 있으므로 dp 배열에서 이미 구한 계산 결과는 재활용해야 한다.

(2) JAVA CODE ☕


class Solution {
    static int n;
    static int [] nums; // 숫자 따로 담는 칸
    static char [] oper; // 연산자 따로 담는 칸
    static int [][][] dp; // [0 = 최대, 1 = 최소][범위 시작 위치][범위 끝 위치]

    public int solution(String arr[]) {
        n = arr.length/2;
        nums = new int [n+1];
        oper = new char [n];
        dp = new int [2][n+1][n+1];

        for(int i = 0; i < arr.length; i++){ // 숫자와 연산자 나눠담기
            if(i%2 == 0) nums[i/2] = Integer.parseInt(arr[i]);
            else oper[i/2] = arr[i].charAt(0);
        }

        for(int i = 0; i < n+1; i++){ // dp 값 초기화 -> 0보다 작은 수도 나올 수 있음으로, 초기화된 것과 안된 것 구분 필요
            for(int j = 0; j < n+1; j++){
                dp[0][i][j] = Integer.MIN_VALUE;
                dp[1][i][j] = Integer.MAX_VALUE;
            }
        }
        return calculate(0, 0, n);
    }

    public int calculate (int flag, int start, int end){
        // 0. base-case (기저 조건)
        if(start == end){ // start == end 일 경우 따로 계산할 필요 없이 원래의 값 넣기
            dp[flag][start][end] = nums[start];
            return dp[flag][start][end];
        }
        // 1. 이미 계산한 값 재활용
        if(isVisited(flag, start, end)) return dp[flag][start][end];

        // 2. 계산 구간
        int result = flag == 0? Integer.MIN_VALUE : Integer.MAX_VALUE;
        if(flag == 0){
            for(int i = start; i < end; i++){ // i는 a + b 관계에서 +,즉 연산자의 위치를 가리킴 (두 집단을 나누는 기준)
                if(oper[i] == '-') result = Math.max(result, calculate(0, start, i) - calculate(1, i+1, end));
                else result = Math.max(result, calculate(0, start, i) + calculate(0, i+1, end));
            }
        }else {
            for(int i = start; i < end; i++){
                if(oper[i] == '-') result = Math.min(result, calculate(1, start, i) - calculate(0,i+1, end));
                else result = Math.min(result, calculate(1, start, i) + calculate(1, i+1, end));
            }
        }
        dp[flag][start][end] = result;
        return dp[flag][start][end];
    }

    public boolean isVisited (int flag, int start, int end){
        return flag == 0? (dp[flag][start][end] != Integer.MIN_VALUE): (dp[flag][start][end] != Integer.MAX_VALUE);
    }


}