[BOJ 16639] 괄호 추가하기 3

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

16639번: 괄호 추가하기 3

 

1. 연산자 우선순위 O

2. 연산자의 갯수 여러개 가능

3. 괄호의 중첩 O

 

3번 조건에 의해서 1번, 2번 조건은 신경 안써도 괜찮다.

1번 -> 우선순위는 괄호를 쳐서 무시하면 되고 ex) 1 + 3 * 2 -> (1 + 3) * 2

2번 -> 연산자가 여러개 있는 건 괄호가 연산자 우선순위대로 쳐져 있는 것과 동일하다 ex) 1 + 3 * 2 == 1 + (3 * 2)

 

어떤 두 식을 연산했을 때

양수 * 양수 = 양수

음수 * 양수 = 음수

양수 * 음수 = 음수

음수 * 음수 = 양수 임을 고려해서

최솟값끼리 연산했을 때 최대가 나올 수 있을 수도 있는 걸 잘 유의해야한다.

 

max_dp(i, j) = i부터 j까지 연산했을 때 최댓값

min_dp(i, j) = i부터 j까지 연산했을 때 최솟값

 

전형적인 O(N^3) dp를 완성하자. -> 유사한 문제 : 파일 합치기, 행렬의 곱셈 순서

 

N = int(input())
E = input()
M = N // 2 + 1
max_dp = [[-10 ** 9] * M for _ in range(M)]
min_dp = [[10 ** 9] * M for _ in range(M)]

for i in range(M):
    max_dp[i][i] = min_dp[i][i] = int(E[i * 2])

for k in range(1,M):
    for i in range(M - k):
        j = i + k
        for x in range(i, j):
            #최댓값
            max_dp[i][j] = max(max_dp[i][j], eval(str(max_dp[i][x]) + E[x * 2 + 1] + str(max_dp[x + 1][j])))
            
            max_dp[i][j] = max(max_dp[i][j], eval(str(min_dp[i][x]) + E[x * 2 + 1] + str(max_dp[x + 1][j])))
            
            max_dp[i][j] = max(max_dp[i][j], eval(str(max_dp[i][x]) + E[x * 2 + 1] + str(min_dp[x + 1][j])))
            
            max_dp[i][j] = max(max_dp[i][j], eval(str(min_dp[i][x]) + E[x * 2 + 1] + str(min_dp[x + 1][j])))

            #최솟값
            min_dp[i][j] = min(min_dp[i][j], eval(str(max_dp[i][x]) + E[x * 2 + 1] + str(max_dp[x + 1][j])))
            
            min_dp[i][j] = min(min_dp[i][j], eval(str(min_dp[i][x]) + E[x * 2 + 1] + str(max_dp[x + 1][j])))
            
            min_dp[i][j] = min(min_dp[i][j], eval(str(max_dp[i][x]) + E[x * 2 + 1] + str(min_dp[x + 1][j])))
            
            min_dp[i][j] = min(min_dp[i][j], eval(str(min_dp[i][x]) + E[x * 2 + 1] + str(min_dp[x + 1][j])))

print(max_dp[0][-1])