백준 16639 괄호 추가하기 3

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

처음에는 완전탐색으로 dfs를 돌렸지만 경우의 수가 많아져 결국 실패했다.

다른 사람의 풀이를 참고했는데,

괄호를 여러개 쓸 수 있다는 점은 연산자의 우선순위에 상관없이 계산을 할 수 있다는 점이다.

그렇기 때문에 어떤식이 있다면 해당 식을

A [op] B 의 형태로 표현할 수 있다.
또한 각각의 A와 B는 다시 A [op] B의 형태로 나뉠 수 있다는 점이다.

그렇기 때문에 A [op] B의 값이 최대가 되기 위해선 각각 A와 B의 최댓값과 최솟값이 필요하다.
이유는 op 가 * 인 경우 둘다 음수인 경우 또는 둘다 양수인 경우가 최대이기 때문이다.

def getValue(start,end):
   res = []
   for pivot in range(start,end):
       if op[pivot] == '+':
           res.append(board[start][pivot][0] + board[pivot+1][end][0])
           res.append(board[start][pivot][0] + board[pivot+1][end][1])
           res.append(board[start][pivot][1] + board[pivot+1][end][0])
           res.append(board[start][pivot][1] + board[pivot+1][end][1])
       elif op[pivot] == '-':
           res.append(board[start][pivot][0] - board[pivot+1][end][0])
           res.append(board[start][pivot][0] - board[pivot+1][end][1])
           res.append(board[start][pivot][1] - board[pivot+1][end][0])
           res.append(board[start][pivot][1] - board[pivot+1][end][1])
       else:
           res.append(board[start][pivot][0] * board[pivot+1][end][0])
           res.append(board[start][pivot][0] * board[pivot+1][end][1])
           res.append(board[start][pivot][1] * board[pivot+1][end][0])
           res.append(board[start][pivot][1] * board[pivot+1][end][1])
   return max(res), min(res)
N = int(input())
n = N // 2
expression = list(input())
num,op = [],[]
for idx,value in enumerate(expression):
   if idx % 2 == 0:
       num.append(int(value))
   else:
       op.append(value)
board = [[[0,0] for i in range(n+1)] for j in range(n+1)]

for offset in range(n+1):
   for start in range(n+1-offset):
       end = start + offset
       if start == end:
           board[start][end][0] = num[start]
           board[start][end][1] = num[start]
       else:
           max_value, min_value = getValue(start,end)
           board[start][end][0] = max_value
           board[start][end][1] = min_value


print(board[0][n][0])