DFS

문제:괄호 추가하기

import sys
input = sys.stdin.readline
n = int(input())
# 숫자는 숫자로 문자는 문자의 형태로 리스트에 저장
lst = [int(v) if i % 2 == 0 else v for i, v in enumerate(list(sys.stdin.readline().rstrip()))]

#eval 함수 사용하기! str의 합으로 사용해야한다.
def ev(num1, oper, num2):
	return eval(str(num1)+oper+str(num2))
#괄호 계산 
# 1+2+3 //  1+(2+3)
def loop(lst, num, idx1, idx2):
	tmp = 0
	if idx2 - idx1 == 4:
		tmp = ev(lst[idx2-2], lst[idx2-1], lst[idx2])
		tmp = ev(num, lst[idx2-3], tmp)
	else:
		tmp = ev(num, lst[idx2-1], lst[idx2])
        # 더이상 계산할 수 없으면 리턴
	if idx2 == n-1:
		return tmp
        # dfs 
	x = loop(lst, tmp, idx2, idx2+2)
	y = loop(lst, tmp, idx2, idx2+4) if idx2+4 < n else x
    	# 둘 중에 큰 거 출력
	return max(x, y)

if len(lst) == 1:
	print(lst[0])
elif len(lst) == 3:
	print(ev(lst[0], lst[1],lst[2]))
else:
	print(max(loop(lst, lst[0], 0, 2), loop(lst, lst[0], 0, 4)))