16637. 괄호 추가하기 (2)

http://boj.kr/16637 

16637번: 괄호 추가하기

 

 

import sys


def _calc(n1, n2, oper):
    if oper == '+':
        return n1 + n2
    elif oper == '-':
        return n1 - n2
    elif oper == '*':
        return n1 * n2


def calc():
    global max_result
    buf = []  # 연산식을 담는데, 괄호는 미리 계산해서 담는다
    
    i = 0
    while i < len(arr):
        if i+2 < len(arr) and paren[i] == paren[i+2] == True:
            tmp = _calc(int(arr[i]), int(arr[i+2]), arr[i+1])  # 괄호 안의 식은 미리 계산
            buf.append(tmp)
            i += 3  
        else:
            if arr[i].isdigit():
                buf.append(int(arr[i]))
            else:
                buf.append(arr[i])
            i += 1

    i = 2
    ret = buf[0]
    while i < len(buf):
        ret = _calc(ret, buf[i], buf[i-1])
        i += 2
    max_result = max(max_result, ret)


def dfs(i):
    while i < len(arr) - 2:  # 마지막 괄호를 쳐볼 수 있는 숫자는 끝에서 두 번째 숫자이다
        if paren[i] == False:
            paren[i] = paren[i+2] = True  # 이번 숫자와, 다음 숫자에 괄호를 표시
            dfs(i+2)
            paren[i] = paren[i+2] = False  # 재귀 함수에서 돌아온 이후에는 괄호를 체크 해제
        i += 2
    calc()
    return


input = sys.stdin.readline
N = int(input())
arr = list(input()[:-1])  # 숫자와 연산자를 모두 한 배열에 담는다.
paren = [False for _ in range(len(arr))]  # 괄호쳤음을 표시
max_result = float('-inf')
dfs(0)
print(max_result)