[BOJ][Java] 백준 16637번: 괄호 추가하기

문제 설명

길이가 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 * -n이 처리가 되지 않기 때문입니다.

따라서 a + b * c 인 경우 (a+b)*c 와 a + (b*c) 이렇게 2가지 케이스로 나눠서 재귀를 돌리면 해결하실 수 있습니다.

 

풀이 코드

import java.util.*;
import java.io.*;

public class BOJ16637 {
    private static int ans = Integer.MIN_VALUE;
    private static final ArrayList<Integer> nums = new ArrayList<>();
    private static final ArrayList<Character> ops = new ArrayList<>();

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

        int N = Integer.parseInt(br.readLine());
        char[] chars = br.readLine().toCharArray();

        for(char ch : chars) {
            if(ch == '+' || ch == '-' || ch == '*') ops.add(ch);
            else nums.add(Character.getNumericValue(ch));
        }

        dfs(nums.get(0), 0);
        System.out.println(ans);
    }

    private static void dfs(int result, int idx) {
        if(idx == ops.size()) {
            ans = Math.max(ans, result);
            return;
        }

        int result1 = calc(ops.get(idx), result, nums.get(idx+1));
        dfs(result1, idx+1);

        if(idx+1 < ops.size()) {
            int result2 = calc(ops.get(idx+1), nums.get(idx+1), nums.get(idx+2));
            dfs(calc(ops.get(idx), result, result2), idx + 2);
        }
    }

    private static int calc(char op, int n1, int n2) {
        switch (op) {
            case '+':
                return n1 + n2;
            case '-':
                return n1 - n2;
            case '*':
                return n1 * n2;
            default:
                return -1;
        }
    }
}

 

<출처>

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

16637번: 괄호 추가하기