백준 16637 괄호 추가하기 (C++)

16637번: 괄호 추가하기

직접 구현을 하는 문제이다. 재귀를 이용해 구현하였다. 괄호를 사용했나 하지 않았나 두가지로 분기하여 재귀를 사용해주었다. pre의 경우 현재 인덱스 포함 이전 까지의 연산 결과를 저장한다. 재귀를 통해 최댓값을 구해 출력해주었다. 굉장히 어려웠던 문제였다. 처음에는 재귀를 통해 괄호를 문자열에 넣어주어 재귀가 끝날 때마다 현재 문자열을 계산하여 최댓값을 구해주려고 생각하였다. 그러나 구현하다보니 시간 초과가 날 것이 명백해보였고 다른 방법을 찾지 못해 결국 다른 블로그를 참고하였다. 아이디어를 참고하니 쉽게 풀 수 있어서 좀 허무했다.... 여러 문제를 풀어봐야 겠다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, result = -2147483648;
string s;

int cal(int a, int b, char oper) {
    int res = a;

    switch (oper) {
    case '+':
        res += b;
        break;
    case '-':
        res -= b;
        break;
    case '*':
        res *= b;
        break;
    }

    return res;
}

void dfs(int index, int pre) {
    if (index > N - 1) {
        result = max(result, pre);
        return;
    }

    char oper = index == 0 ? '+' : s[index - 1];

    if (index < N - 2) {
        int bracket = cal(s[index] - '0', s[index + 2] - '0', s[index + 1]);
        dfs(index + 4, cal(pre, bracket, oper));
    }
    dfs(index + 2, cal(pre, s[index] - '0', oper));
}

void solution() {
    dfs(0, 0);
    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> s;

    solution();

    return 0;
}