[백준]16639. 괄호 추가하기 3

[백준]16639. 괄호 추가하기 3

📄 링크

괄호 추가하기 3

---

💡 문제 분석

수식을 입력받고 여기에 괄호를 임의로 추가하여 최대값을 구하는 문제입니다

이 문제의 핵심은 괄호를 마음대로 넣을 수 있기 때문에 연산자의 우선순위는 아무런 의미가 없다는 것입니다. 그렇기 때문에 괄호를 넣을 수 있는 모든 방법으로 완전 탐색을 진행하고 캐시에 저장해서 해결하였습니다

하지만 이 문제에서 *연산을 할 때 음수 * 음수를 했을 때 가장 큰 수가 나올 수 있기 때문에 가장 작은 값들도 계속 저장을 하고 있어야합니다.

1. Calc(max, max)
2. Calc(max, min)
3. Calc(min, max)
4. Calc(min, min)

• 4가지 계산을 모두 해서 가장 큰 수는 max 캐시에, 가장 작은 수는 min 캐시에 저장합니다

---

⌨️ 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main_Taekyung2 {
    static int[][] max, min;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        char[] s = sc.next().toCharArray();
        max = new int[N][N];
        min = new int[N][N];
        for(int i = 0; i < N; i++) {
            Arrays.fill(max[i], Integer.MIN_VALUE);
            Arrays.fill(min[i], Integer.MAX_VALUE);
        }
        for(int i = 0; i < N; i++) {
            if(Character.isDigit(s[i])) {
                max[i][i] = s[i] - '0';
                min[i][i] = s[i] - '0';
            }
        }
        for(int j = 2; j < N; j+=2) {
            for(int i = 0; i < N - j; i+=2) {
                for(int k = 2; k <= j; k+=2) {
                    int[] num = new int[4];
                    int op = i + k - 1;
                    num[0] = calc(max[i][i + k - 2], max[i + k][i + j], s[op]);
                    num[1] = calc(max[i][i + k - 2], min[i + k][i + j], s[op]);
                    num[2] = calc(min[i][i + k - 2], max[i + k][i + j], s[op]);
                    num[3] = calc(min[i][i + k - 2], min[i + k][i + j], s[op]);
                    Arrays.sort(num);
                    max[i][i + j] = Math.max(max[i][i + j], num[3]);
                    min[i][i + j] = Math.min(min[i][i + j], num[0]);
                }
            }
        }
        System.out.println(max[0][N - 1]);
    }

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

---

📋 결과