[Programmers] P1843 사칙연산

[Programmers] P12905 사칙연산

Question

Language: Python

행렬최소곱셈횟수와 비슷한 유형의 문제로

아래와 같은 정규식을 통해 문제를 풀이를 할 수 있다. f_i,j=min(f_i,k operator f_k+1,j)[i<=k<=j]

이때, operator는 중간에 위치한 연산자의 종류에 따라 가게 되므로 조건문을 통해 따로 분리해야한다. 아래의 예시를 통해, 경우에 따라 적용되는 연산자의 종류가 다른 것을 확인할 수 있다.

1 - 3 + 5

경우 1: (1-3) + 5
경우 2: 1 - (3+5)

또한, 행렬과 다르게 음수 * 음수의 결과를 통해 큰 양수가 나오는 경우가 발생하므로, 각각의 중간 연산 과정에서 min/max 값 두 개 모두 저장하고 아래와 같은 조합을 고려해야한다.

min op min
min op max
max op min
max op max

Solution

from math import inf
def solution(arr):
    operands=[]
    operators=[]

    for segment in arr:
        if segment in ["+","-"]:
            operators.append(segment)
        else:
            operands.append(int(segment))

    num=len(operands)    
    #각각의 공간에 대해서 최소,최대값을 저장한다.
    dp=[[[inf,-inf] for _ in range(num+1)] for _ in range(num+1)]
    
    #대각선(i,i)에 대해서는 자기 자신의 값을 저장한다.
    for i in range(1,num+1):
        dp[i][i][0]=operands[i-1]
        dp[i][i][1]=operands[i-1]

    for diagonal in range(1,num+1):
        for i in range(1,num-diagonal+1):
            j=i+diagonal
            tmp=[]
            for k in range(i,j):
                #중간 연산자가 + 인 경우
                if operators[k-1]=="+":
                    values=[dp[i][k][0]+dp[k+1][j][0],dp[i][k][0]+dp[k+1][j][1],dp[i][k][1]+dp[k+1][j][0],dp[i][k][1]+dp[k+1][j][1]]           
                    dp[i][j][0]=min(dp[i][j][0],min(values))
                    dp[i][j][1]=max(dp[i][j][1],max(values))
                #중간 연산자가 - 인 경우
                elif operators[k-1]=="-":
                    values=[dp[i][k][0]-dp[k+1][j][0],dp[i][k][0]-dp[k+1][j][1],dp[i][k][1]-dp[k+1][j][0],dp[i][k][1]-dp[k+1][j][1]]
                    dp[i][j][0]=min(dp[i][j][0],min(values))
                    dp[i][j][1]=max(dp[i][j][1],max(values))
    
    return max(dp[1][-1])