[알고리즘][X][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
    # 어떻게 선택하는게 최선일지 모르기 때문에 그리디는 패스
    # 괄호를 넣는 것도 경로가 가야할 방향이 불확실하기 때문에 패스
    # 그럼 DP
    # 길이가 201개 밖에 안된다 상당히 짧다. for문을 여러번 써도 괜찮다
    # 숫자에 집중해야 할 거 같다. 숫자가 묶이는 순서에 집중하자.
    # 예제를 보면 드는 생각은 우선 더하기를 진행하고 뺄셈은 나중에 진행하는게 좋다는 생각이다.
    # 관건은 -와 - 사이에 있는 +들을 어떤 순서로 처리할 지인 듯하다.
    # 일단 + 는 
    # DP는 완전탐색에 이용

---

참고해서 푼 풀이

- dp를 두 개를 쓴게 핵심

- if step == 0: 부분에서 max_dp는 설정했는데 min_dp는 설정을 안했음. 이거 찾는데 되게 오래 걸림

- 알고리즘이 적용되는 순서는 다음과 같다.

예를 들어, 10 - 5 + 7 - 5가 주어지면

step 0은 생략하고 step 1부터 10 - 5, 5 + 7, 7 - 5가 계산된다.

step2는 10 - 5 + 7, 5 + 7 -5가 계산되는데 이때, 10 - 5 + 7을 계산하기 위해서는 (10 - 5) + 7이든 10 - (5 + 7)이든 두가지가 가능하다. 근데 10 - 5와 5 + 7은 이미 step 1에서 계산했기 때문에 계산 과정을 담은 dp 배열을 참고해서 구하게 된다.

step3도 마찬가지이다.

결국 앞에서 얻었던 결과를 재활용해서 다음 연산에 쓰기 때문에 DP인 것이다.

def solution(arr):
    inf = int(1e9)
    
    n_number = len(arr) // 2 + 1
    n_op = len(arr) // 2
    
    max_dp = [[-inf for i in range(n_number)] for j in range(n_number)]
    min_dp = [[inf for i in range(n_number)] for j in range(n_number)]
    
    for step in range(len(max_dp)):
        for i in range(len(max_dp) - step):
            j = i + step
            
            if step == 0:
                max_dp[i][i] = int(arr[2*i])
                min_dp[i][i] = int(arr[2*i])
            else:
                for k in range(i, j):
                    if arr[2*k+1] == "+":
                        max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j])
                        min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j])                 
                    elif arr[2*k+1] == "-":
                        max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k+1][j])
                        min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k+1][j])              
                        
    return max_dp[0][n_number-1]

Reference

---

https://school.programmers.co.kr/questions/35224