[알고리즘][2][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 입니다.

나의 풀이

- 어려운 문제

- dp를 for문에서 사용할 때는 중간 연산자가 이미 계산된 적이 있도록 즉 쌓아지도록 설계해야 한다는 것을 배웠다.

- 처음에는 [1][2] [1][3] [1][4] 이렇게 했는데 이렇게 되면 [1][4]를 계산할 때 필요한 [1][2][2] 등은 아직 계산이 되지 않은 상태이다.

- for문 순서가 헷갈리긴 한다. 순서를 아무렇게 해도 되는지 아니면 저렇게 해야 하는지

import math

def solution(arr):
    # 최대를 구하는 문제이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수는 없으므로 그리디 X
    # 그래프 탐색을 하려면 만약 101개의 숫자가 있다고 한다면 (1, 100), (2, 99), (3, 98) ... 이고 그 안에서도
    # (1, (1, 99)), (1, (99, 1)) 등 나누어지므로 ! 단위가 되기 때문에 힘들다.
    # 그러나 중간 연산을 계속 활용하기 때문에 DP를 활용하면 된다.
    # 4개인 경우를 생각해보자
    # (1, 3), (2, 2), (3, 1)
    # (1, (1, 2)) (1, (2, 1)), ((1, 1), (1, 1)), ((2, 1), 1), ((1, 2), 1)
    # (1, (1, (1, 1))), (1, ((1,1), 1)) ((1, 1), (1, 1)), (((1, 1), 1), 1), ((1, (1, 1)), 1)
    # f(4)에 최댓값이 담겨 있기 위해서는 (1, 3), (2, 2), (3, 1) 중 가장 큰 값을 선택해야 한다.
    # 또한 각각은 ,가 -라면 앞은 최대, 뒤는 최소, ,가 +라면 앞은 최대, 뒤도 최대가 되어야 한다.
    # 따라서 최대 DP, 최소 DP를 운영해야 한다.
    # 12 23 34 13 24 14
    
    # max_dp[i][j]는 i부터 j까지의 최댓값
    max_dp = [[-float(math.inf)] * ((len(arr)//2)+2) for _ in range((len(arr)//2)+2)]
    min_dp = [[float(math.inf)] * ((len(arr)//2)+2) for _ in range((len(arr)//2)+2)]
    
    for i in range(1, (len(arr)//2)+2):
        max_dp[i][i] = int(arr[2*(i-1)])
        min_dp[i][i] = int(arr[2*(i-1)])
        
    
    for j in range(1, (len(arr)//2)+2):
        for i in range(1, (len(arr)//2)+2):
            for k in range(1, i+j):
                if i+j >= (len(arr)//2)+2:
                    continue
                if arr[2 * k - 1] == "+":
                    max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] + max_dp[k+1][i+j])
                    min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] + min_dp[k+1][i+j])
                elif arr[2 * k - 1] == "-":
                    max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] - min_dp[k+1][i+j])
                    min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] - max_dp[k+1][i+j])
    
    return max_dp[1][-1]

이 코드는 리팩토링한 코드

import math

def solution(arr):
    # 최대를 구하는 문제이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수는 없으므로 그리디 X
    # 그래프 탐색을 하려면 만약 101개의 숫자가 있다고 한다면 (1, 100), (2, 99), (3, 98) ... 이고 그 안에서도
    # (1, (1, 99)), (1, (99, 1)) 등 나누어지므로 ! 단위가 되기 때문에 힘들다.
    # 그러나 중간 연산을 계속 활용하기 때문에 DP를 활용하면 된다.
    # 4개인 경우를 생각해보자
    # (1, 3), (2, 2), (3, 1)
    # (1, (1, 2)) (1, (2, 1)), ((1, 1), (1, 1)), ((2, 1), 1), ((1, 2), 1)
    # (1, (1, (1, 1))), (1, ((1,1), 1)) ((1, 1), (1, 1)), (((1, 1), 1), 1), ((1, (1, 1)), 1)
    # f(4)에 최댓값이 담겨 있기 위해서는 (1, 3), (2, 2), (3, 1) 중 가장 큰 값을 선택해야 한다.
    # 또한 각각은 ,가 -라면 앞은 최대, 뒤는 최소, ,가 +라면 앞은 최대, 뒤도 최대가 되어야 한다.
    # 따라서 최대 DP, 최소 DP를 운영해야 한다.
    # 12 23 34 13 24 14
    
    # max_dp[i][j]는 i부터 j까지의 최댓값
    n = len(arr)//2 + 2
    max_dp = [[-float(math.inf)] * n for _ in range(n)]
    min_dp = [[float(math.inf)] * n for _ in range(n)]
    
    for i in range(1, n):
        max_dp[i][i] = int(arr[2*(i-1)])
        min_dp[i][i] = int(arr[2*(i-1)])
        
    
    for j in range(1, n):
        for i in range(1, n):
            for k in range(1, i+j):
                if i+j >= n:
                    continue
                if arr[2 * k - 1] == "+":
                    max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] + max_dp[k+1][i+j])
                    min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] + min_dp[k+1][i+j])
                elif arr[2 * k - 1] == "-":
                    max_dp[i][i+j] = max(max_dp[i][i+j], max_dp[i][k] - min_dp[k+1][i+j])
                    min_dp[i][i+j] = min(min_dp[i][i+j], min_dp[i][k] - max_dp[k+1][i+j])
    
    return max_dp[1][-1]