[ 백준 16637 ] 괄호 추가하기 ( 자바 )

[ 백준 16637 ] 괄호 추가하기 ( java ) 

길이가 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은 홀수이다.

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

 

 

 

출처: 백준, https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

 

핵심 

1 완탐 

N이 최대 19로 모든 연산자에 괄호를 할지 말지 고려해도 시간제한을 통과할 수 있다. 

dfs, bfs 여러 방법으로 해결할 수 있다. 

 

2 dfs / dfs+메모이제이션

2-1 dfs + 메모이제이션 

dfs로 모든 op에서 괄호를 할지 말지를 메모이제이션에 기록한다. 

그리고, 하나의 메모이제이션이 완성되면 계산하기 

 

2-3 dfs 

동일하게 모든 op에 괄호 할지 말지를 고려하는데, 계산을 하며 진행한다. 

현재 괄호를 치게 된다면, 직전 op를 취소하고 다시 계산해야하지만, 굳이 그렇게 하지 않고 직접 값도 들고 다녔다. 

 

 

3 주의 

1) 계산 결과나 너무 큰 값이 나온적이 있는데, char 피연산자를 int로 바꾸지 않아 매우 큰 값이 나왔었다. 

2) 문제 특성 상 괄호 유무 처리 시, 인덱스 범위 주의 하기 

3) 처음, 시작, 최소 입력

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        input = br.readLine().toCharArray();
        
        dfs(1, input[0]-'0', 0, false);
        System.out.println(max);
    }
    static int N;
    static char[] input;
    static int max = Integer.MIN_VALUE;
    static void dfs(int op_i, int val, int pre_val, boolean wasBrace) {
        
        if(op_i >= N) {
            if(max < val)
                max = val;
            return;
        }
        // 현재 괄호 x
        dfs(op_i+2, cal(val, input[op_i], input[op_i+1]-'0'), val, false);
        
        // 현재 괄호 칠 수 있나? 되면 침 
        if(op_i > 1 && !wasBrace) {
            dfs(op_i+2, cal(pre_val, input[op_i-2], cal(input[op_i-1]-'0', input[op_i], input[op_i+1]-'0')),
                    0, true);
        }
        
    }
    static int cal(int a, char op, int b) {
        if(op == '+') return a + b;
        else if(op == '-') return a - b;
        else return a * b;
    }
}