[BOJ] 백준 16637번 : 괄호 추가하기 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/16637

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))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

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

 

풀이

DFS와 백트래킹을 이용하여 풀 수 있는 문제였습니다. 처음부터 괄호로 묶을 대상을 모두 뽑아놓고, 브루트포스를 돌리는 것도 좋은 판단이지만, 저는 처음부터 모두 괄호로 묶는 경우를 구현하기 어려워서 백트래킹을 사용하였습니다.

2가지 경우에 대해서 재귀 함수를 돌리시면 됩니다.

1. 이전의 연산 결과를 순서대로 계산함.

2. 이전의 연산 결과 오른쪽에 있는 2개의 값을 괄호로 처리하여 계산하고 이전의 연산 결과와 합침.

이 두 가지를 DFS 내에서 구현하시면 됩니다.

연산하는 함수는 단순하게 switch ~ case로 +, -, *일 때 경우를 나누어서 계산하면 편하지만, 위에서 말한 백트래킹은 바로 이해하기는 어렵기때문에 아래에서 더 자세히 알아보겠습니다.

 

DFS + 백트래킹 추가 설명

// DFS, 백트래킹 활용.
    public static void DFS(int result, int opIdx) {
        // 주어진 연산자의 개수를 초과하였을 경우.
        if (opIdx >= ops.size()) {
            ans = Math.max(ans, result);
            return;
        }
 
        // 괄호가 없는 경우
        int res1 = calc(ops.get(opIdx), result, nums.get(opIdx + 1));
        DFS(res1, opIdx + 1);
 
        // 괄호가 있는 경우
        if (opIdx + 1 < ops.size()) {
            // result의 오른쪽에 있는 값을 연산함.
            int res2 = calc(ops.get(opIdx + 1), nums.get(opIdx + 1), nums.get(opIdx + 2));
 
            // 현재 result와 방금 구한 괄호 값을 연산한 결과와 괄호 오른쪽에 존재하는 연산자의 인덱스를 넘김.
            DFS(calc(ops.get(opIdx), result, res2), opIdx + 2);
        }
    }

위 코드가 제가 말한 괄호를 묶었을 때와 묶지 않았을 때 연속적으로 계산하는 함수입니다.

먼저, 예를 들어 input이 3 + 8 * 7 - 9 * 2 가 들어왔다고 합시다.

여기서 연산자와 숫자를 따로 ArrayList에 담았습니다. 전자는 ops = {+, *, -, *}, 후자는 num = {3, 8, 7, 9, 2}와 같습니다.

처음에는 3부터 시작합니다.

일단, 괄호가 없다고 가정하여 3 + 8 = 11을 수행합니다.

그리고 11 * 7 - 9 * 2 과정이 쭉쭉 진행되다가 종료조건을 만나서 ans = 136이 될 것입니다.

이 후에는 맨 뒤부터 괄호를 묶을 수 있는 경우 묶으면서 연속적으로 계산하면 됩니다.

먼저, 3 + 8 * 7 - (9 * 2)가 수행될 것이므로 이전 연산 결과 77과 -18을 계산하여 59를 반환합니다.

끝까지 계산에 도달했으므로 ans와 59 중 큰 것으로 초기화합니다.

그리고 3 + 8 * (7 - 9) * 2가 수행될 것이므로 이전 연산 결과 11과 -2를 계산하여 9를 반환합니다.

끝까지 계산에 도달한 것이 아니므로 9 * 2 = 18을 계산하고, ans와 18 중 큰 것으로 초기화합니다.

다음으로, 3 + (8 * 7) - 9 * 2가 수행될 것이므로 이전 연산 결과 3과 8 * 7을 계산하여 59를 반환합니다.

끝까지 계산에 도달한 것이 아니므로 59 - 9 * 2를 계산하거나, 59 - (9 * 2)를 계산할 수 있습니다.

위와 같은 방식으로 2개의 값과 ans 중 큰 것으로 초기화하면 모든 과정이 끝납니다.

아래 소스코드를 보시면서 차근 차근 디버깅해 보시길 바랍니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
 
public class Main {
    static int ans;
    static ArrayList<Character> ops;
    static ArrayList<Integer> nums;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        String input = br.readLine();
 
        ops = new ArrayList<>();
        nums = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                ops.add(c);
                continue;
            }
            nums.add(Character.getNumericValue(c));
        }
 
        ans = Integer.MIN_VALUE;
        DFS(nums.get(0), 0);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 연산
    public static int calc(char op, int n1, int n2) {
        switch (op) {
        case '+':
            return n1 + n2;
        case '-':
            return n1 - n2;
        case '*':
            return n1 * n2;
        }
        return -1;
    }
 
    // DFS, 백트래킹 활용.
    public static void DFS(int result, int opIdx) {
        // 주어진 연산자의 개수를 초과하였을 경우.
        if (opIdx >= ops.size()) {
            ans = Math.max(ans, result);
            return;
        }
 
        // 괄호가 없는 경우
        int res1 = calc(ops.get(opIdx), result, nums.get(opIdx + 1));
        DFS(res1, opIdx + 1);
 
        // 괄호가 있는 경우
        if (opIdx + 1 < ops.size()) {
            // result의 오른쪽에 있는 값을 연산함.
            int res2 = calc(ops.get(opIdx + 1), nums.get(opIdx + 1), nums.get(opIdx + 2));
 
            // 현재 result와 방금 구한 괄호 값을 연산한 결과와 괄호 오른쪽에 존재하는 연산자의 인덱스를 넘김.
            DFS(calc(ops.get(opIdx), result, res2), opIdx + 2);
        }
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.