[백준 16639번] 괄호 추가하기 3 (Python)

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)인 위의 풀이보다는 훨씬 느리다. 그래서 파이썬에서는 이 방식을 사용하면 시간초과가 발생하였다.