BOJ)괄호 추가하기 3

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

 

시간복잡도를 확인하고 브루트포스로 해결하려했지만 실패했다.

결국 다른 사람의 코드를 참고하여 풀었고, 이해하는데 조금 애를 먹었다.

 

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])

 

max_dp[i][j]는 i부터 j까지(숫자들)의 계산 중 가장 큰 값이 들어가고, min_dp[i][j]는 i부터 j까지의 수의 계산 중 가장 작은 값이 들어간

다.

이 문제의 핵심은 반례를 생각하는 것이다.

 

일반적으로 큰 숫자 * 큰숫자로 가장 큰 숫자를 만들 수 있지만,계산하여 나온 마이너스 값 * 계산하여 나온 마이너스 값의 경우 가장 큰 값이 될 수 있기 때문이다.

때문에 계산 값중 가장 큰 값과 가장 작은 값을 따로 저장해야 이 문제를 풀 수가있다.

 

우선 코드를 보면 이해가 안되지만 직접 반복문의 로그를 찍어보면 이해가 간다.

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

우선 위 코드로 dp배열에 n으로 받은 수를 넣어준다.

 

그럼 위와 같은 배열이 된다.

우선 max,min은 생각하지 않겠다.

 

그 다음 반복문 하나하나를 보며 i,j,x,min_dp[i][j], max_dp[i][j]의 값을 보면 다음과 같다.

 

위 코드를 보면 다음과 같은 규칙이 존재한다.

 

 

이때 중요한 것은 min_dp와 max_dp의 [i][j]는 각각 max_dp와 min_dp를 비교해가며 최소/최대값을 갱신한다.

이런 식으로 max_dp[0][-1]는 3부터 2까지의 계산 값 중 가장 큰 값이 들어가게된다.