백준 괄호 추가하기

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다.
둘째 줄에는 수식이 주어진다.
수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다.
문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다.
연산자는 +, -, * 중 하나이다.
여기서 *는 곱하기 연산을 나타내는 × 연산이다.
항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

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

내가 이 문제를 보고 생각해본 부분

expr는 입력된 수식의 문자 배열로, 홀수 인덱스에는 연산자, 짝수 인덱스에는 숫자가 위치한다
dfs 함수는 현재 연산자의 인덱스와 현재까지 누적된 계산 값을 받아 다음 연산을 수행한다
dfs에서 먼저 괄호 없이 다음 숫자를 바로 계산하는 경우를 시도한다.
그리고 괄호 추가가 가능한 경우, 현재 연산자와 다음 연산자 사이의 두 숫자를 괄호로 묶어 먼저 계산한 값을 사용해 재귀 호출한다.
괄호 안에는 반드시 연산자가 하나만 있어야 하므로, 괄호는 연산자 하나와 그 양쪽 숫자 두 개를 감싼다.
최종적으로 모든 연산자를 처리하면 maxResult를 갱신하며, 이를 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

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

// 백준 16637번 문제
public class Main1345 {
    static int N;
    static char[] expr;
    static int maxResult = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        expr = br.readLine().toCharArray();

        int firstNum = expr[0] - '0';

        // 재귀 호출: 첫 숫자부터 시작
        dfs(1, firstNum);

        System.out.println(maxResult);
        br.close();
    }

    // idx: 현재 연산자 위치 (항상 홀수 인덱스), curVal: 현재까지 계산된 값
    static void dfs(int idx, int curVal) {
        // 모든 연산 처리 완료 시 최대값 갱신
        if (idx >= N) {
            if (curVal > maxResult)
                maxResult = curVal;
            return;
        }

        // 연산자
        char op = expr[idx];

        // 다음 숫자 (괄호 없이 바로 계산)
        int nextNum = expr[idx + 1] - '0';
        int val1 = calc(curVal, op, nextNum);
        dfs(idx + 2, val1);

        // 괄호 추가 가능 여부: 다음 연산자가 있고, 괄호 안에는 연산자 하나만 있어야 하므로 2개 숫자와 1개 연산자를 괄호로 묶음
        if (idx + 2 < N) {
            char nextOp = expr[idx + 2];
            int nextNextNum = expr[idx + 3] - '0';

            // 괄호 안 계산: nextNum op nextNextNum 을 먼저 계산
            int bracketVal = calc(nextNum, nextOp, nextNextNum);
            int val2 = calc(curVal, op, bracketVal);

            dfs(idx + 4, val2);
        }
    }

    static int calc(int a, char op, int b) {
        switch (op) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
        }
        return 0; // 기본
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.