[C++] 백준 16637 괄호 추가하기

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> num;
vector<char> oper_str;
int n, ret = INT_MIN;
string s;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int oper(char a, int b, int c) {
    if (a == '+') return b + c;
    if (a == '-') return b - c;
    if (a == '*') return b * c;
    return 0;
}

void go(int here, int _num) {
    if (here == num.size() - 1) {
        ret = max(ret, _num);
        return;
    }
    go(here + 1, oper(oper_str[here], _num, num[here + 1]));
    
    if (here + 2 <= num.size() - 1) {
        int temp = oper(oper_str[here + 1], num[here + 1], num[here + 2]);
        go(here + 2, oper(oper_str[here], _num, temp));
    }
}

int main() {
    fastIO();
    cin >> n;
    cin >> s;
    
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) num.push_back(s[i] - '0');
        else oper_str.push_back(s[i]);
    }
    
    go(0, num[0]);
    cout << ret << "\n";
    return 0;
}

풀이

N개의 길이를 가진 수식이 주어졌을 때, 괄호를 적절히 추가하여 최대 결과값을 구하는 문제입니다.

• 수식은 정수 (0~9)와 연산자 (+, -, ×) 로 이루어져 있음.
• 연산자 우선순위는 모두 동일하므로, 왼쪽에서 오른쪽으로 순서대로 계산해야 함.
• 괄호를 추가 가능하지만 괄호 안에는 하나의 연산자만 포함 가능.
• 괄호를 중첩할 수 없음.

1) 숫자와 연산자를 분리

for (int i = 0; i < n; i++) {
    if (i % 2 == 0) num.push_back(s[i] - '0'); // 숫자 저장
    else oper_str.push_back(s[i]); // 연산자 저장
}

2) 연산 수행 함수

int oper(char a, int b, int c) {
    if (a == '+') return b + c;
    if (a == '-') return b - c;
    if (a == '*') return b * c;
    return 0;
}

3) 괄호를 추가하는 모든 경우를 탐색

void go(int here, int _num) {
    if (here == num.size() - 1) { 
        ret = max(ret, _num); // 최댓값 갱신
        return;
    }
    
    // 괄호 없이 연산하는 경우
    go(here + 1, oper(oper_str[here], _num, num[here + 1]));
    
    // 괄호를 추가하는 경우
    if (here + 2 <= num.size() - 1) {
        int temp = oper(oper_str[here + 1], num[here + 1], num[here + 2]);
        go(here + 2, oper(oper_str[here], _num, temp));
    }
}

핵심 정리
✔ 괄호 없이 연산하는 경우 + 괄호를 추가하는 경우를 모두 탐색
✔ 재귀(DFS)로 모든 괄호 추가 방법을 고려
✔ 최대 결과값을 ret에 저장하여 정답 출력
✔ 연산 우선순위 없이 왼쪽부터 계산하므로 괄호가 중요