[Baekjoon] 괄호 추가하기 3(python)

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

문제 접근

파일합치기 문제와 비슷한 방식으로 DP를 통해 해결하려고 시도했다.

 

내가 생각해내지 못했던 것은 연산자에 대한 인덱스 처리와 연산자에 따라 최솟값을 이용해서 최댓값을 만들 수 있는 경우가 있다는 것을 놓치고 있었고 검색을 통하여 힌트를 얻어 문제를 해결했다.

---

풀이 과정

문제를 푸는 핵심 개념은 Bottom-Up 방식으로 수식을 작은 범위부터 큰 범위로 확장해나가면서 계산하면 된다.

 

각 구간별 최댓값을 DP 배열에 저장하면서 구간을 확장하면 결국 DP[n][n]에 우리가 구하고자 하는 값이 저장될 것이다.

위의 그림을 코드로 표현하면 아래와 같을 것이다.

 

n은 전체 수식에서 피연산자 갯수를 구한 것이고 (수식의 길이 + 1) // 2가 된다.

 

따라서 각 구간별 연산자 인덱스를 구하려면 2 * k + 1이 된다.

for j in range(1, n):
    for i in range(j - 1, -1, -1):
        for k in range(i, j):
            dp[i][j] = max(dp[i][j], calculate(dp[i][k], dp[k + 1][j], expressions[2 * k + 1]))

하지만 이렇게만 계산하면 틀린다.

 

동그라미 안에 들어갈 연산자에 따라서 무엇이든 최댓값이 될 수 있는 경우가 생기기 때문이다.

 

따라서 최솟값을 저장하는 DP 배열과 최댓값을 저장하는 DP 배열를 만들어 각 구간별 연산 결과를 저장해야 한다.

 

또 각 구간별 연산자에 대해

 

(최댓값) - (최댓값)

(최댓값) - (최솟값)

(최솟값) - (최댓값)

(최솟값) - (최솟값)

 

4가지 경우를 모두 계산해서 최댓값과 최솟값을 갱신하여야 정확한 답을 구할 수 있다.

 

이에 따라 코드를 수정하면 다음과 같다.

for j in range(1, n):
    for i in range(j - 1, -1, -1):
        for k in range(i, j):

            values = sorted([
                calculate(max_dp[i][k], max_dp[k + 1][j], expressions[2 * k + 1]),
                calculate(max_dp[i][k], min_dp[k + 1][j], expressions[2 * k + 1]),
                calculate(min_dp[i][k], max_dp[k + 1][j], expressions[2 * k + 1]),
                calculate(min_dp[i][k], min_dp[k + 1][j], expressions[2 * k + 1]),
            ])

            max_dp[i][j] = max(max_dp[i][j], values[-1])
            min_dp[i][j] = min(min_dp[i][j], values[0])

---

정답 코드

"""
    백준 16639번 괄호 추가하기 3
"""
import sys

N = int(sys.stdin.readline())
expressions = sys.stdin.readline()

n = (N + 1) // 2

max_dp = [[-sys.maxsize] * n for _ in range(n)]
min_dp = [[sys.maxsize] * n for _ in range(n)]

def calculate(a, b, operator):
    if operator == "+":
        return a + b
    elif operator == "-":
        return a - b
    elif operator == "*":
        return a * b

for i, s in enumerate(expressions):
    if not s.isdigit():
        continue

    min_dp[i // 2][i // 2] = max_dp[i // 2][i // 2] = int(s)

for j in range(1, n):
    for i in range(j - 1, -1, -1):
        for k in range(i, j):

            values = sorted([
                calculate(max_dp[i][k], max_dp[k + 1][j], expressions[2 * k + 1]),
                calculate(max_dp[i][k], min_dp[k + 1][j], expressions[2 * k + 1]),
                calculate(min_dp[i][k], max_dp[k + 1][j], expressions[2 * k + 1]),
                calculate(min_dp[i][k], min_dp[k + 1][j], expressions[2 * k + 1]),
            ])

            max_dp[i][j] = max(max_dp[i][j], values[-1])
            min_dp[i][j] = min(min_dp[i][j], values[0])


print(max_dp[0][-1])