[프로그래머스] 사칙연산

https://school.programmers.co.kr/learn/courses/30/lessons/1843

프로그래머스

해설

• 연산 기호를 기준우로 좌우로 놔누면서 재귀를 호출한다
• 연산을 하면서 Max값과 Min값을 계속해서 기록한다
• 연산 기호를 기준으로 max값과 min값을 계산한다

MAX_DP = [[-987654321 for _ in range(201+1)] for _ in range(201+1)]
MIN_DP = [[987654321 for _ in range(201+1)] for _ in range(201+1)]

def solution(arr):
    answer,_ = dfs(arr,0,len(arr)-1)
    return answer


def doCalculate(a,b,c):
    A = int(a)
    B = int(c)
    if b == '-':
        return A-B
    else:
        return A+B

def dfs(arr,start,end):
    if MAX_DP[start][end] != -987654321 and MIN_DP[start][end] != 987654321:
        return MAX_DP[start][end] , MIN_DP[start][end]
    if start == end:
        MAX_DP[start][end] = int(arr[start])
        MIN_DP[start][end] = int(arr[start])
        return MAX_DP[start][end] , MIN_DP[start][end]
    
    for i in range(start,end,2):
        leftMax, leftMin = dfs(arr,start,i)
        rightMax,rightMin = dfs(arr,i+2,end)
        if arr[i+1] == "+":
            MAX_DP[start][end] = max(MAX_DP[start][end], leftMax+rightMax)
            MIN_DP[start][end] = min(MIN_DP[start][end], leftMin+rightMin)
        else:
            MAX_DP[start][end] = max(MAX_DP[start][end], leftMax-rightMin)
            MIN_DP[start][end] = min(MIN_DP[start][end], leftMin-rightMax)
    return MAX_DP[start][end], MIN_DP[start][end]