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

괄호 추가하기_16637

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

16637번: 괄호 추가하기

문제 설명

수식이 주어진다. 수식은  0~9사이의 정수와 연산자(+, -, x)로 이루어져있다.

연산자의 우선순위는 모두 같다.

괄호를 사용하여 최대값을 구하는데 조건이 있다.

 

1. 하나의 괄호에 두개의 연산자를 사용할 수 없다.

1+(2x3)+4+5 : 가능

1+(2x3+4)+5 : 불가능

 

2. 괄호를 중첩해서 사용할 수 없다.

1+(2x3)+(4x5) - 가능

1+((2x3)+4)x5 - 불가능

 

괄호를 적절히 사용하여 만들 수 있는 최댓값을 구하는 문제이다.

---

문제 풀이

생각 과정

수식의 길이가 N으로 주어지는데 길이가 최대 19개밖에 되지 않는다.

10개의 숫자와 9개의 연산자만 계산하면 되므로 브루트포스로 전부 계산해주기로 했다.

 

수식을 앞에서부터 보는데 괄호가 없는 경우는 앞에서부터 계산하고

괄호가 있는 경우는 뒤의 숫자 두개를 먼저 계산해주고 맨 앞 숫자를 따로 계산해준다. 

직접 수식을 보는게 이해가 편하다.

이런 과정을 거쳐 최댓값을 구할 수 있다.

 

이를 코드로 구현하는 방식은 인덱스를 이용하여 구현했다.

run함수를 생성했고

첫번째 파라미터는 현재까지 구한 합을 넣어놨고

두번째 파라미터는 현재 인덱스를 넣어둔다.

 

시작은 run(0,0)으로 시작하여

위에서 말한 두가지 경우를 재귀로 반복한다.

현재까지의 합 = sum

현재 인덱스 = idx

1. 괄호를 사용하는 경우 : run( sum과 첫번째 숫자의 계산, idx+2)

<숫자 하나,연산자 하나 사용했으므로 인덱스를 2칸이동>

2. 괄호를 사용안하는 경우 : run(sum과 [첫번째 숫자와 두번째 숫자를 계산한 것]의 계산 , idx+4 )

<숫자 둘,연산자 둘 사용했으므로 인덱스를 4칸이동>

 

재귀의 종료조건은 현재 인덱스가 수식의 범위를 벗어난 경우이다.

 

구현

public class 괄호추가하기_16637 {
    static int answer;
    static int N;
    static char[] chars;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        answer = Integer.MIN_VALUE;
        N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        chars = new char[N + 1];
        chars[0] = '+';	
        for (int i = 0; i < str.length(); i++) {
            chars[i+1] = str.charAt(i);
        }
        run(0, 0);
        System.out.println(answer);
    }

    public static void run(int sum, int idx) {
        if (idx > N) {
            answer = Math.max(answer, sum);
            return;
        }
        char ope1 = chars[idx];
        int a = chars[idx + 1] - '0';
        // 괄호 미사용 - 앞에서부터 계산
        run(cal(sum, ope1, a), idx + 2);
        // 괄호 사용 - 뒤에서부터 계산
        if (idx+2<=N){
            char ope2 = chars[idx+2];
            int b = chars[idx + 3] - '0';
            run(cal(sum, ope1, cal(a, ope2,b)), idx + 4);
        }
    }

    public static int cal(int a, char ope ,int b) {
        if (ope == '+') return a + b;
        else if (ope == '-') return a - b;
        else return a * b;
    }
}

주의점

최대값이 음수가 나올 수 있으므로 기본 최댓값을 Integer.MIN_VALUE로 설정해놔야 했는데 생각없이 초기화를 안해줘서 0으로 설정됐었다. 생각하자