[백준] 16639번. 괄호 추가하기3(JAVA)

문제

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

---

풀이

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

public class Main {

    static int N;
    static char[] expression;
    static int[][] dpMin, dpMax;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            N = Integer.parseInt(br.readLine());
            expression = br.readLine().toCharArray();
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }

        dpMin = new int[N][N];
        dpMax = new int[N][N];

        initializeDP();

        for (int j = 2; j < N; j += 2) {
            for (int i = 0; i < N - j; i += 2) {
                calculateMinMax(i, j);
            }
        }

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

    static void initializeDP() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(dpMin[i], Integer.MAX_VALUE);
            Arrays.fill(dpMax[i], Integer.MIN_VALUE);
        }
        for (int i = 0; i < N; i += 2) {
            int number = expression[i] - '0';
            dpMax[i][i] = number;
            dpMin[i][i] = number;
        }
    }

    static void calculateMinMax(int start, int offset) {
        for (int k = 2; k <= offset; k += 2) {
            char operator = expression[start + k - 1];
            int[] results = new int[4];

            results[0] = calculate(dpMax[start][start + k - 2], dpMax[start + k][start + offset], operator);
            results[1] = calculate(dpMax[start][start + k - 2], dpMin[start + k][start + offset], operator);
            results[2] = calculate(dpMin[start][start + k - 2], dpMax[start + k][start + offset], operator);
            results[3] = calculate(dpMin[start][start + k - 2], dpMin[start + k][start + offset], operator);

            Arrays.sort(results);
            dpMax[start][start + offset] = Math.max(dpMax[start][start + offset], results[3]);
            dpMin[start][start + offset] = Math.min(dpMin[start][start + offset], results[0]);
        }
    }

    static int calculate(int a, int b, char operator) {
        switch (operator) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            default: throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}

 

 문제를 접하고, 일반적인 괄호 풀이처럼 큐 혹은 스택을 이용해서 문제를 해결하려고 했다. 하지만 마지막 예제에 대한 오류가 지속적으로 발생했고, dp로 해결할 수 있다고 생각했다.

 

문자를 지속적으로 검사하며 동적 검사를 진행한다. 이후 가능한 최대 값을 출력한다.

또한, 코딩테스트를 대비하여 예외처리 검사 로직도 진행한다.