[알고리즘][3][RE] 사칙연산

문제 설명
사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

((1 - 5) - 3) = -7
(1 - (5 - 3)) = -1
위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

(((1 - 3) + 5) - 8) = -5
((1 - (3 + 5)) - 8) = -15
(1 - ((3 + 5) - 8)) = 1
(1 - (3 + (5 - 8))) = 1
((1 - 3) + (5 - 8)) = -5
위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호("+"), 뺄셈 기호("-")가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항
arr는 두 연산자 "+", "-" 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
arr의 길이는 항상 홀수입니다.
arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : "456")
배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.
입출력 예
arr	result
["1", "-", "3", "+", "5", "-", "8"]	1
["5", "-", "3", "+", "1", "+", "2", "-", "4"]	3
입출력 예시
입출력 예 #1
위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.

입출력 예 #2
(5-(3+((1+2)-4))) = 3 입니다.

나의 풀이

- 맞기는 맞았는데 디버깅이 안돼서 한참 헤맸다.

- 그 이유는 코드가 나 자신도 못알아보게 너무나 복잡했던 것이다.

- 코테를 보며 복잡한 구현에 약하다는 것도 알았다.

- 따라서 이 문제를 통해 가독성을 높이고 스스로가 알아볼 수 있게 단순하게 풀 수 있는 연습을 하겠다.

def solution(arr):
    # 최댓값이므로 그리디, DP, 탐색
    # 그리디 X
    # 탐색 X
    # DP
    
    n = len(arr) // 2 + 1
    op_n = len(arr)
    inf = int(1e9)
    max_dp = [[-inf] * (1 + n) for _ in range(1 + n) ]
    min_dp = [[inf] * (1 + n) for _ in range(1 + n) ]
    for i in range(1, n+1):
        max_dp[i][i] = int(arr[(i-1)*2])
        min_dp[i][i] = int(arr[(i-1)*2])
        
    for step in range(1, n+1):
        for i in range(1, n-step+2):
            for j in range(step-1):
                if arr[(i-1+j)*2+1] == "+":
                    max_dp[i][i+step-1] = max(max_dp[i][i+step-1], max_dp[i][i+j] + max_dp[i+j+1][i+step-1])
                    min_dp[i][i+step-1] = min(min_dp[i][i+step-1], min_dp[i][i+j] + min_dp[i+j+1][i+step-1])
                else:
                    max_dp[i][i+step-1] = max(max_dp[i][i+step-1], max_dp[i][i+j] - min_dp[i+j+1][i+step-1])
                    min_dp[i][i+step-1] = min(min_dp[i][i+step-1], min_dp[i][i+j] - max_dp[i+j+1][i+step-1])                  
    
    
    return max_dp[1][-1]