import sys
input = sys.stdin.readline
def cal(a,x,b):
if x == "*":
return int(a)*int(b)
if x == "+":
return int(a)+int(b)
if x == "-":
return int(a)-int(b)
def DFS(SUM,n):
global result
if n == N:
result = max(result,SUM)
return
if n < N-1:
DFS(cal(SUM,eq[n*2+1],cal(eq[n*2+2],eq[n*2+3],eq[n*2+4])),n+2)
DFS(cal(SUM,eq[n*2+1],eq[n*2+2]),n+1)
N = int(input())
N //= 2
eq = input().strip()
result = -sys.maxsize
DFS(int(eq[0]),0)
print(result)
괄호 추가하기 2번 문제가 있길래 1은 어떤 문제인지 궁금해서 한번 풀어보았다.
1과 2의 차이는 곱하기의 우선순위인데 1번문제인 만큼 우선순위 차이가 없다 보니 쉽게 해결할 수 있었다.
브루트 포스를 통해 n//2개의 연산자에 대해서 i번째 연산을 할 때, i+1번 연산을 먼저 하고 i번째 연산을 하는 경우와 그냥 i번째 먼저 연산을 하는 두 가지 경우의 수로 나누어 풀 수 있다.
오늘의 교훈) 괄호 추가하기 2를 풀어보자