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

1.  문제 링크

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

2.  문제

요약

• 길이가 N인 수식이 있는데, 수식은 0보다 크거나 같고 9보다 작거나 같은 정수와 연산자 +, -, ×로 이루어져 있습니다.
• 연산자 우선순위는 모두 동일하므로 수식을 계산할 때는 왼쪽에서부터 순서대로 계산합니다.
• 수식에 괄호가 추가되면 괄호 안에 있는 식을 먼저 계산해야 하는데, 괄호 안에는 연산자가 하나만 들어있어야 합니다.
• 중첩된 괄호는 사용할 수 없습니다.
• 수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 최댓값을 구하는 문제입니다.
• 추가하는 괄호 개수의 제한은 없고, 추가하지 않아도 됩니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 19보다 작거나 같은 수식의 길이 N이 주어지고 두 번째 줄에 수식이 주어집니다.
  • 수식에 포함된 정수는 모두 0보다 크거나 같고 9보다 작거나 같습니다.
  • 수식은 정수로 시작하고, 연산자와 정수가 번갈아가며 나옵니다.
  • 항상 올바른 수식만 주어지므로 N은 홀수입니다.
• 출력: 첫 번째 줄에 괄호를 적절히 추가해 얻을 수 있는 결과의 최댓값을 출력합니다. 답은 $2^{31}$보다 작고, $-2^{31}$보다 큽니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, answer;
    static ArrayList<Integer> operands;
    static ArrayList<Character> operators;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        String expression = scanner.nextLine();
        operators = new ArrayList<>();
        operands = new ArrayList<>();
        for(int idx = 0; idx < N; idx++) {
            if(idx % 2 == 0) operands.add(expression.charAt(idx) - '0');
            else operators.add(expression.charAt(idx));
        }
    }

    static void solution() {
        answer = Integer.MIN_VALUE;
        dfs(operands.get(0), 0);
        System.out.println(answer);
    }

    static void dfs(int result, int index) {
        if(index >= operators.size()) {
            answer = Math.max(answer, result);
            return;
        }
        int temp = calculation(operators.get(index), result, operands.get(index + 1));
        dfs(temp, index + 1);
        if(index + 1 < operators.size()) {
            int temp2 = calculation(operators.get(index + 1), operands.get(index + 1), operands.get(index + 2));
            dfs(calculation(operators.get(index), result, temp2), index + 2);
        }
    }

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

    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;
        }
    }
}

4.  접근

• DFS를 이용하여 괄호를 친 경우와 그렇지 않은 경우 각각에 대해서 값을 계산하여 최종적으로 최댓값을 구합니다.
  • 괄호를 치지 않은 경우에는 현재까지 탐색하면서 얻은 수식의 결과에 다음 수를 계산하여 이 결과를 다음 계산에 이용합니다.
  • 괄호를 친 경우에는 현재 탐색하는 수의 다음 수와 그 다음 수에 대해서 먼저 계산을 한 뒤에 현재까지 탐색하면서 얻은 수식에 계산된 값을 이용하여 계산하여 이 결과를 다음 계산에 이용합니다.
• 위 방법으로 괄호를 칠 수 있는 곳에 괄호를 추가해보면서 수식의 마지막 수까지 계산하고 그렇게 구한 결과 중 가장 큰 값을 출력합니다.