사칙연산

• 행렬 연쇄 곱셈 문제와 비슷한 방식으로 DP를 이용해서 O(n^3)에 푸는 방법이 쉽게 떠오른다. 공식 해설조차도 이 방법을 답으로 제시하고 있다
• 그러나 사칙 연산의 특성을 이용하면 훨씬 간단한 방법으로 O(n)에 푸는 것이 가능하다.
• +연산자만 있을때에는 괄호를 어떻게 붙이든지 결과값은 동일하다. -연산자의 경우는 그 뒤에 이어지는 n개의 텀을 괄호로 묶으면, 그 사이에 있는 n-1개의 연산자의 계산 방법이 +는 -로, -는 +로 비뀐다고 생각할 수 있다.
• 그러면 구체적인 예를 들어 생각하자. 우선 식에 -가 1개만 있으면, 즉 a1+a2+…+an-b1+b2+…+bm 이런 경우이면, -뒤의 연산자들은 모두 +이니 -로 바꿔줄 필요가 없다. 즉 괄호를 그냥 하나도 안붙여서 -가 붙는 텀을 b1 하나로 끝내는 것이 최적이다
• 식에 -가 두개 있으면, 즉 a1+a2+…+an-b1+b2+…+bm-c1+c2+…+cl 이런 경우이면, b1앞의 -를 이용해서 연산자들을 바꿔줄 범위는, 괄호를 안붙여서 아무것도 안 바꾸던가, b1부터 c1까지를 괄호로 묶어서 그 사이에 있는 연산자들을 모두 바꾸던가 둘중의 하나를 선택해야 한다. c1이 b2+b3+…+bm 보다 크면 모두 바꾸는게 이득이고, 그렇지 않으면 안바꾸는게 이득이다. 괄호를 c1을 포함시키지 않고 애매하게 bi까지만 바꾸는 것은 -를 +로 바꾸는 것 없이 +를 -로 바꾸기만 할 뿐이므로 당연히 안바꾸는 것보다 손해이다. 따라서 선택지로 고려할 필요가 없다.
• 일반화시켜서, 괄호를 b2~bi까지만 묶는 경우는 선택지에 없으므로, b2,b3,…,bm 까지는 앞에 붙는 부호가 항상 같게 유지된다. 설명을 쉽게 하기 위해서 b2+b3+..+bm 을 미리 괄호로 묶었다고 생각하고 하나의 텀으로 표현해도 문제가 없다.
• 이렇게 해서, 식을 일반화해서 y[n+1]-x[n]+y[n]-x[n-1]+y[n-1]-…-x[2]+y[2]-x[1]+y[1] 이라고 쓰자.
• 하나 더 알아둘 것은, x[i] 앞에 있는 -의 적용 범위를, y[i]까지 포함시킬 경우의 최댓값은 그 뒤에 있는 모든 항이 +가 되는 것이다. 예를 들어 y[n]을 -로 처리하는 것을 감수한다면, x[1] ~ x[n-1], y[1] ~ y[n-1]은 모두 +로 만들수 있다.
  • y[n+1] - (x[n] + y[n] -(x[n-1] + y[n-1]) - …. -(x[2] + y[2]) -(x[1] + y[1]))
    = y[n+1] - x[n] - y[n] + x[n-1] + y[n-1] + …. + x[2] + y[2] + x[1] + y[1]
• 이제 그럼 점화식을 세울수 있다. dp_sum[i] = x[i]+y[i]+x[i-1]+y[i-1]+…+x[1]+y[1] 로 정의하고. dp_max[i]는 -x[i]+ y[i]-x[i-1]+y[i-1]-…-x[1]+y[1]에 괄호를 붙여서 만들수 있는 최댓값으로 두자. 점화식은 이렇게 된다.
  • dp_max[i] = -x[i] + max(y[i]+dp_max[i-1], -y[i]+dp_sum[i-1])
• 최종 결과값은 y[n+1] + dp_max[n] 이다.
• 이 식은 O(n)에 계산 가능하다.

"""Solution code for "Programmers 1843. 사칙연산".

Greedy solution, running in O(n).
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/1843
- Solution link: http://www.teferi.net/ps/problems/programmers/1843
"""


def solution(arr):
    cur_sum = prev_max = prev_sum = 0
    for sign, num in zip(arr[-2::-2], arr[-1::-2]):
        num = int(num)
        if sign == '+':        
            cur_sum += num
        else:
            prev_max = -num + max(cur_sum + prev_max, -cur_sum + prev_sum)
            prev_sum += cur_sum + num
            cur_sum = 0
    return int(arr[0]) + cur_sum + prev_max

"""Solution code for "Programmers 1843. 사칙연산".

DP solution, running in O(n^3).
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/1843
- Solution link: http://www.teferi.net/ps/problems/programmers/1843
"""

INF = float('inf')


def solution(arr):
    n = len(arr) // 2 + 1
    dp_max = [[-INF] * n for _ in range(n)]
    dp_min = [[INF] * n for _ in range(n)]
    for i, num in enumerate(arr[::2]):
        dp_max[i][i] = dp_min[i][i] = int(num)
    sign = arr[1::2]

    for l in range(1, n):
        for i in range(n - l):
            j = i + l
            for k in range(i, j):
                if sign[k] == '+':
                    dp_max[i][j] = max(dp_max[i][j],
                                       dp_max[i][k] + dp_max[k + 1][j])
                    dp_min[i][j] = min(dp_min[i][j],
                                       dp_min[i][k] + dp_min[k + 1][j])
                else:
                    dp_max[i][j] = max(dp_max[i][j],
                                       dp_max[i][k] - dp_min[k + 1][j])
                    dp_min[i][j] = min(dp_min[i][j],
                                       dp_min[i][k] - dp_max[k + 1][j])
    return dp_max[0][-1]