[알고리즘] 괄호 추가하기

포인트

• 연산자 기준으로 재귀가 실행됩니다. 
• 재귀, dfs, 완전탐색, 백트랙킹 은 비슷한 분류
• 재귀를 생각하는 조건을 조금 더 알아보자

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

cpp/c++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int n, operation;
int answer = -987654321;
int num[21];
char oper[21];

int calc(int a, int b, char input) {
    if (input == '+') return a + b;
    if (input == '-') return a - b;
    if (input == '*') return a * b;
}

void go(int index, int result) {
    if (index >= operation) { // 인덱스가 연산을 넘어가면 종료 조건
        answer = max(answer, result);
        return;
    }

    int xResult = calc(result, num[index + 1], oper[index]);
    go(index + 1, xResult);

    if (index + 1 < operation) {
        int nxResult = calc(num[index + 1], num[index + 2], oper[index + 1]);
        int re = calc(result, nxResult, oper[index]);
        go(index + 2, re);
    }
}

int main() {

    cin >> n;
    int index1 = 0;
    int index2 = 0;

    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (i % 2 == 0) {
            num[index1] = s[i] - '0';
            index1 += 1;
        } else {
            oper[index2] = s[i];
            index2 += 1;
        }
    }
    operation = n / 2;

    if (n == 1) {
        cout << num[0] << '\n';
        return 0;
    } else if (n == 3) {
        cout << calc(num[0], num[1], oper[0]) << '\n';
        return 0;
    }

    go(0, num[0]);
    cout << answer << '\n';

}

python

def calc(a: int, b: int, oper: str) -> int:
    if oper == '+':
        return a + b
    elif oper == '-':
        return a - b
    elif oper == '*':
        return a * b


def go(index: int, result: int) -> None:
    global answer
    if index >= operation:
        answer = max(answer, result)
        return

    x = calc(result, num[index + 1], oper[index])
    go(index + 1, x)

    if index + 1 < operation:
        nx = calc(num[index + 1], num[index + 2], oper[index + 1])
        re = calc(result, nx, oper[index])
        go(index + 2, re)


n = int(input())
s = input()

index1 = 0
index2 = 0
oper = []
num = []

for char in s:
    if char.isnumeric():
        num.append(int(char))
    else:
        oper.append(char)

operation = n // 2
if n == 1:
    print(num[0])
elif n == 3:
    result = calc(num[0], num[1], oper[0])
    print(result)
else:
    answer = -987654321
    go(0, num[0])
    print(answer)