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

문제 소개

괄호 추가하기 - 백준 16637번 문제를 정리합니다.
이 문제는 연산자 우선순위가 없는 수식에서 괄호를 적절히 추가해 최댓값을 만드는 완전탐색 유형입니다.
문제의 핵심은 괄호는 연산자 하나만 포함해야 하며, 중첩 불가라는 제약을 고려해 가능한 모든 연산 순서를 탐색하는 데 있습니다.

문제 링크: 괄호 추가하기 - 백준 16637번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 피연산자와 연산자 분리
   • 홀수 위치는 숫자, 짝수 위치는 연산자로 나뉘므로 배열로 분리
2. DFS를 이용한 모든 경우의 수 탐색
   • 현재 연산을 실행하는 경우
   • 뒤에 괄호를 묶어서 먼저 연산한 값을 현재와 연산하는 경우
3. 괄호는 중첩 불가
   • 다음 연산을 괄호로 묶는 경우는 한 칸을 건너뛴 인덱스로 이동

---

해결 과정 및 코드

핵심 아이디어

1. 수식을 좌→우로 계산하는 기본 로직은 cal(pre, op, next)
2. 괄호를 쓰지 않는 경우는 현재 값과 다음 피연산자를 연산자와 함께 계산
3. 괄호를 쓰는 경우는 (operand[idx+1] op operand[idx+2])를 먼저 계산하고, 그 값을 현재 값과 다시 연산
4. 이렇게 DFS로 연산을 순차적으로 시도하면서 가능한 모든 결과를 탐색
5. 최대값은 전역 변수 maxCal에 계속 갱신

코드

시간 복잡도 : O(2^(N/2))

import java.io.*;

public class Main {
    static int[] operand;          // 숫자 배열
    static char[] operator;        // 연산자 배열
    static int maxCal = Integer.MIN_VALUE; // 최댓값 저장

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

        // 수식 파싱: 숫자와 연산자 분리
        operand = new int[N / 2 + 1];
        operator = new char[N / 2];
        int opd = 0, opr = 0;
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) operand[opd++] = input.charAt(i) - '0';
            else operator[opr++] = input.charAt(i);
        }

        // DFS 시작
        calDFS(operand[0], 0);
        System.out.println(maxCal);
    }

    // 연산 함수
    static int cal(int num1, char op, int num2) {
        switch (op) {
            case '+': return num1 + num2;
            case '-': return num1 - num2;
            case '*': return num1 * num2;
        }
        return 0;
    }

    // DFS 탐색 함수
    static void calDFS(int pre, int idx) {
        if (idx >= operator.length) {
            maxCal = Math.max(maxCal, pre); // 끝까지 도달하면 최댓값 갱신
            return;
        }

        // 1. 괄호 없이 계산
        int noBracket = cal(pre, operator[idx], operand[idx + 1]);
        calDFS(noBracket, idx + 1);

        // 2. 괄호 사용하는 경우: 뒤의 두 숫자를 먼저 계산한 결과를 현재와 계산
        if (idx + 1 < operator.length) {
            int bracket = cal(operand[idx + 1], operator[idx + 1], operand[idx + 2]);
            int withBracket = cal(pre, operator[idx], bracket);
            calDFS(withBracket, idx + 2);
        }
    }
}

 

---

참고 : 비슷한 문제 - [프로그래머스] 사칙연산

https://orion-log.tistory.com/53

[프로그래머스] 사칙연산 (분할 정복 + DP)

 

단

백준 16637번은 괄호는 연산자 1개만 포함 가능, 중첩 불가 / 기본 왼쪽 -> 오른쪽 순으로 연산처리

반면 사칙연산 최댓값 문제는 연산 순서를 마음대로 바꿀 수 있음

👉 따라서 단순 DFS로 괄호만 하나 씌우고 한 칸 건너뛰는 식으로는 전체 탐색이 불가능