백준 16637 괄호 추가하기

https://www.acmicpc.net/problem/16637

dfs로 해결하는 전략을 택했다.

문제를 일반화시켜보면,

a op b op c 와 같은 형태로 생각할 수 있다.
이러한 상황에서 괄호는 앞에 걸거나, 뒤에걸거나 둘중 하나이다.
이 정보를 토대로 재귀적인 방법으로 앞에 괄호를 했다면 뒤에는 하지 못하게 재귀를 돌고,
뒤에 괄호를 했다면 앞에 괄호를 하지 못하게 하면 된다.

import math
n = int(input())
exp = input()
nums = []
operator = []
for e in exp:
    if e.isdigit():
        nums.append(e)
    else:
        operator.append(e)
answer = -math.inf
def solve(idx,local_sum):
    global answer
    if idx == len(operator):
        answer = max(answer, int(local_sum))
        return local_sum
    ## 앞에 괄호를 묶는경우
    left = eval(local_sum + operator[idx] + nums[idx+1])
    left = str(left)
    solve(idx + 1, left)

    ## 뒤에 괄호를 묶는경우, 연산자 2개는 있어야함
    if idx + 1 < len(operator):
        _right = eval(nums[idx+1] + operator[idx+1] + nums[idx+2])
        right = eval(local_sum + operator[idx] + str(_right))
        right = str(right)
        solve(idx + 2, right)
solve(0,nums[0])
print(answer)