[BaekJoon] 16639 괄호 추가하기 3 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/16639

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static char[] expression;
    static int[][] min, max;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        // min[start][end] = start번째부터 end번째까지의 계산 중 가장 작은 계산값
        // max[start][end] = start번째부터 end번째까지의 계산 중 가장 큰 계산값
        min = new int[N][N];
        max = new int[N][N];
        for(int idx = 0; idx < N; idx++) {
            Arrays.fill(min[idx], Integer.MAX_VALUE);
            Arrays.fill(max[idx], Integer.MIN_VALUE);
        }

        String expressionStr = scanner.nextLine();
        expression = expressionStr.toCharArray();
        for(int idx = 0; idx < N; idx += 2) {
            int operand = expressionStr.charAt(idx) - '0';
            min[idx][idx] = max[idx][idx] = operand;
        }
    }

    static void solution() {
        // start ~ end까지의 계산 결과는 start ~ middle까지의 결과 + middle ~ end까지의 결과와 같다
        // 그러므로 start부터 end 사이에 중간 위치들을 하나씩 잡아보면서
        // start부터 중간 위치까지의 계산값, 중간 위치부터 end까지의 계산값을 이용하여 연산자에 맞는 연산을 진행하고
        // 해당 연산에서 나온 계산값들을 통해 min, max를 갱신해나간다
        for(int endLength = 2; endLength < N; endLength += 2) {
            for(int start = 0; start < N - endLength; start += 2) {
                for(int middleLength = 2; middleLength <= endLength; middleLength += 2) {
                    char operator = expression[start + middleLength - 1];
                    List<Integer> tentativeResults = new ArrayList<>();

                    tentativeResults.add(calculate(min[start][start + middleLength - 2], min[start + middleLength][start + endLength], operator));
                    tentativeResults.add(calculate(min[start][start + middleLength - 2], max[start + middleLength][start + endLength], operator));
                    tentativeResults.add(calculate(max[start][start + middleLength - 2], min[start + middleLength][start + endLength], operator));
                    tentativeResults.add(calculate(max[start][start + middleLength - 2], max[start + middleLength][start + endLength], operator));

                    Collections.sort(tentativeResults);

                    min[start][start + endLength] = Math.min(min[start][start + endLength], tentativeResults.get(0));
                    max[start][start + endLength] = Math.max(max[start][start + endLength], tentativeResults.get(tentativeResults.size() - 1));
                }
            }
        }

        System.out.println(max[0][N - 1]);
    }

    static int calculate(int operand1, int operand2, char operator) {
        if (operator == '+') {
            return operand1 + operand2;
        } else if(operator == '-') {
            return operand1 - operand2;
        } else {
            return operand1 * operand2;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";

            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}