[백준] 16637 괄호 추가하기 - Brute Force / Java

• 문제 링크

16637번: 괄호 추가하기

 

• 풀이 과정

재귀 호출 함수를 통해 다음 연산에 괄호를 사용해 연산할 지, 그대로 연산할 지 두가지 경우를 모두 계산한다.

 

크기가 수식의 길이 n 인 char 배열 input 을 생성해 입력받은 수식을 저장한 후,

인덱스 변수를 idx 로 정의하고 정수의 경우 input[idx] - '0' 로 호출, 연산자는 input[idx] 로 호출한다.

 

호출한 정수와 연산자에 맞게 연산값을 반환할 cal 함수를 생성하고,

연산의 결과가 누적될 값 res, input 배열을 탐색할 인덱스 값 idx 를 재귀 함수 recur 의 매개 변수로 지정한다.

 

예시로 A + B * C 의 수식이 존재할 경우, 초기 res 값은 A 가 되고,

괄호를 사용하지 않을 시 A + B 의 값을 res 값으로써 재귀 함수에 전달하거나,

괄호를 사용 시 B * C 의 값을 먼저 구한 후, A + (B * C) 의 값을 res 값으로써 재귀 함수에 전달하는 두 경우가 있다.

 

이렇게 괄호가 생성될 수 있는 각각의 분기마다 모든 경우를 구해 연산한 후,

연산의 결과값을 max 값과 비교하여 최대값으로 갱신하여 max 의 최종값을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    static int n;
    static int max = Integer.MIN_VALUE;
    static char[] input;

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

        n = Integer.parseInt(br.readLine());
        input = new char[n];
        input = br.readLine().toCharArray();

        recur(input[0] - '0', 2);

        bw.write(max + "\n");
        bw.flush();
    }

    private static void recur(int res, int idx) {
        if (idx >= n) {
            max = Math.max(max, res);
            return;
        }

        recur(cal(res, input[idx] - '0', input[idx - 1]), idx + 2);

        if (idx + 2 < n) {
            int bracket = cal(input[idx] - '0', input[idx + 2] - '0', input[idx + 1]);
            recur(cal(res, bracket, input[idx - 1]), idx + 4);
        }
    }

    private static int cal(int x, int y, char op) {
        if (op == '+')
            return x + y;
        else if (op == '-')
            return x - y;
        else
            return x * y;
    }

}