[백준] 16637. 괄호 추가하기 - python

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

16637번: 괄호 추가하기

난이도: 골드3

알고리즘: DP

 

풀이과정

 

처음에는 최대값을 저장하는 DP를 구성해서 풀이해봤습니다.

 

 

예제 1번은 다음와 같이 계산할 수 있습니다.

 

cache에는 최대값이 저장되고 괄호를 적용했을 때와 적용하지 않았을 때를 비교해 큰 값을 취합니다

.

하지만 위와 같이 최대 값만을 적용하다보면 문제가 있습니다.

 

19
2*1-1*1+2*2-9*8-9*9

 

 

이는 질문게시판에 있는 반례로 위와 같이 최대값만을 갱신하면 답이 27로 나오지만

 

최소값에 음수를 곱하여 최대를 만드는 경우가 존재하기 때문에 답은 189가 나옵니다

.

따라서 최대값을 저장하는 max_cache와 최소값을 저장하는 min_cache를 둬서 값을 갱신했습니다

.

max_cache = max(최대 - 괄호 미적용, 최대 - 괄호 적용, 최소 - 괄호 미적용, 최소 - 괄호 적용)

min_cache = min(최대 - 괄호 미적용, 최대 - 괄호 적용, 최소 - 괄호 미적용, 최소 - 괄호 적용)

 

위와 같이 점화식을 구성하면 정상적으로 최대값을 구할 수 있습니다.

 

 

소스코드

N = int(input())
row = input()
if N == 1:
    print(int(row[0]))
    exit()

max_cache = [0 for _ in range((N // 2) + 1)]
min_cache = [0 for _ in range((N // 2) + 1)]

max_cache[0] = int(row[0])
min_cache[0] = int(row[0])
if row[1] == '+':
    max_cache[1] = min_cache[1] = int(row[0]) + int(row[2])
elif row[1] == '-':
    max_cache[1] = min_cache[1] = int(row[0]) - int(row[2])
elif row[1] == '*':
    max_cache[1] = min_cache[1] = int(row[0]) * int(row[2])

idx = 2
def cal(num1, exp, num2):
    if exp == '+':
        return num1 + num2
    elif exp == '-':
        return num1 - num2
    elif exp == '*':
        return num1 * num2


for i in range(4, N, 2):
    num1 = int(row[i - 2])
    exp1 = row[i - 3]
    num2 = int(row[i])
    exp2 = row[i - 1]
    max_cache[idx] = max(cal(max_cache[idx - 1], exp2, num2), cal(max_cache[idx - 2], exp1, cal(num1, exp2, num2)),
                        cal(min_cache[idx - 1], exp2, num2), cal(min_cache[idx - 2], exp1, cal(num1, exp2, num2)))
    min_cache[idx] = min(cal(max_cache[idx - 1], exp2, num2), cal(max_cache[idx - 2], exp1, cal(num1, exp2, num2)),
                        cal(min_cache[idx - 1], exp2, num2), cal(min_cache[idx - 2], exp1, cal(num1, exp2, num2)))
    idx += 1

print(max_cache[idx - 1])