괄호추가하기

누적합을 활용한 완전탐색
연산자와 숫자를 각각 다른 ArrayList에 값을 받아준다.

3 + 8 * 5

위 식은 2가지로 괄호로 묶어줄 수 있다.

(1) (3 + 8) * 5

(2) 3 + (8 * 5)

(1),(2)식을 고대로 dfs의 재귀함수로 표현하면 된다.
재귀함수 이므로 종료조건 기준을 넣어준다. 기준은 모든 수를 다 돌때까지 이다.

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;

public class Main {

    static ArrayList<Character> oper_str;
    static ArrayList<Integer> nums;

    static int N;

    static String s;

    static int res;

    // 완전탐색
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        s = br.readLine();

        res = Integer.MIN_VALUE;
        oper_str = new ArrayList<>();
        nums = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            if(i%2 == 0){
                nums.add(s.charAt(i)-'0'); //
            }else{
                oper_str.add(s.charAt(i));
            }
        }

        go(0,nums.get(0)); // 시작점
        bw.write(String.valueOf(res)+'\n');
        bw.flush();
        bw.close();
        br.close();
    }

    public static void go(int here, int num){ // index를 기준으로

        if(here == nums.size()-1){ // 끝까지 다 돈 경우
            res = Math.max(res,num);
            return;
        }

        // 앞의 값을 먼저 계산
        go(here + 1, oper(oper_str.get(here), num, nums.get(here+1)));

        if(here + 2 <= nums.size() - 1){ // 뒤에꺼 괄호해주기 - 오버플로우 체크
            int temp = oper(oper_str.get(here+1), nums.get(here+1),nums.get(here+2)); // 뒤에 값을 먼저 계산
            go(here+2, oper(oper_str.get(here), num, temp)); // 앞에 같이 계산한 값 더해주기
        }
    }

    public static int oper(char a, int b, int c){
        if(a == '+') return b + c;
        if(a == '-') return b - c;
        else return b*c;
    }
}

모를땐 재귀함수에 일일히 디버깅해보면서 하자!