N = int(input())//2+1; eq = input()
DP = [[[1e12,-1e12] for i in range(N)] for i in range(N+1)]
DP[1] = [(int(eq[i*2]),int(eq[i*2])) for i in range(N)]
for l in range(2,N+1):
for i in range(N-l+1):
for ll in range(1,l):
for m1 in range(2):
for m2 in range(2):
x = eval(str(DP[ll][i][m1])+eq[(i+ll)*2-1]+str(DP[l-ll][i+ll][m2]))
DP[l][i] = min(DP[l][i][0],x),max(DP[l][i][1],x)
print(DP[N][0][1])
DP로 해결하였다.
행렬 곱셈 순서 [백준 11049번] 행렬 곱셈 순서 (Python3) (tistory.com) 와 비슷한 방식으로 해결할 수 있다.
풀이를 설명하면,
1. DP[l][i]는 i번째 숫자부터 l개의 숫자를 연산했을 때의 최솟값과 최댓값을 의미한다.
2. 행렬 곱셈 순서 문제를 풀듯이, i~i+l까지의 숫자들 중 하나를 기준으로 양 옆을 계산했을 때 최솟값과 최댓값을 bottom-up DP로 구한다.
3. DP[N][0]의 최댓값을 출력한다.
주의할 점은 가운데의 기호가 마이너스인 경우 최댓값을 얻기 위해서 최솟값이 필요한 경우가 생긴다. 따라서 행렬곱셈순서 문제와 다르게 최댓값과 최솟값을 모두 구해주어야 한다.
사실 이 문제는 N이 최대 10으로 굉장히 작기 때문에 아래와 같은 브루트 포스로도 해결할 수 있다.
input(); q = [input()]; result = -1e12
while q:
eq = q.pop()
if len(eq)==1:
result = max(result,int(eq[0]))
for i in range(len(eq)//2):
eq1 = [*eq]
eq1[i*2:i*2+3] = [str(eval("".join(eq1[i*2:i*2+3])))]
q.append(eq1)
print(result)
그러나 이 풀이는 시간복잡도가 O(N!)이라서 O(N^3)인 위의 풀이보다는 훨씬 느리다. 그래서 파이썬에서는 이 방식을 사용하면 시간초과가 발생하였다.