[BOJ16637/Java] 괄호 추가하기

[Gold III] 괄호 추가하기 - 16637

문제 링크

성능 요약

메모리: 11640 KB, 시간: 76 ms

분류

브루트포스 알고리즘, 구현

제출 일자

2023년 10월 17일 14:31:24

• 문제

  문제 설명

  길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

  수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

  수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

  입력

  첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

  출력

  첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -2보다 크다.

---

문제 요약

1. 수식의 홀수번째 인덱스에는 연산자가 온다
2. 수식에 추가하는 괄호는 연산자가 하나만 들어있어야 한다. 또한 중첩된 괄호는 사용할 수 없다.
3. 연산의 기본 순서는 왼쪽부터

접근 아이디어

하나의 연산자에 괄호를 적용한다면 그 다음 연산자는 괄호를 적용할 수 없다. 중첩된 괄호는 사용할 수 없기 때문이다. 여기서 시작해서 이전 연산자의 괄호 적용 여부를 체크한 뒤, 지금 연산자에 괄호를 적용할 때, 적용하지 않을 때를 나눠서 계산하는 방식으로 구현했다.

또한 각 분기 별로 계산결과가 달라지기 때문에 deque에 현재 계산 상태를 복사해서 다르게 분기될 수 있도록 했다.

작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static char[] expression;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        expression = br.readLine().toCharArray();

        Deque<Integer> num = new ArrayDeque<>();
        Deque<Character> oper = new ArrayDeque<>();

        num.push(expression[0] - '0');
        dfs(1, false, num, oper);

        System.out.println(max);
    }

    static void dfs(int idx, boolean flag, Deque<Integer> num, Deque<Character> oper) {
        if (idx == N) {
            while (!oper.isEmpty()) {
                int first = num.removeLast();
                char o = oper.removeLast();
                int second = num.removeLast();
                num.add(calc(first, second, o));
            }
            int res = num.pop();
            if (res > max) {
                max = res;
            }
            return;
        }

        Deque<Integer> tnum = new ArrayDeque(num);
        Deque<Character> toper = new ArrayDeque(oper);

        if (flag) { // 이전 연산자에서 괄호를 적용함
            // 이번 연산자에서는 괄호 적용할 수 없음
            // 그럼 나랑 내 다음 연산자 넣고 다음으로 넘어가기
            tnum.push(expression[idx + 1] - '0');
            toper.push(expression[idx]);
            dfs(idx + 2, false, tnum, toper);
        } else {
            // 괄호 적용 o
            int t = tnum.pop();
            tnum.push(calc(t, expression[idx + 1] - '0', expression[idx]));
            dfs(idx + 2, true, tnum, toper);

            // 괄호 적용 x
            num.push(expression[idx + 1] - '0');
            oper.push(expression[idx]);
            dfs(idx + 2, false, num, oper);
        }
    }

    static int calc(int a, int b, char c) {
        switch (c) {
        case ('+'):
            return a + b;
        case ('-'):
            return a - b;
        default:
            return a * b;
        }
    }
}