[PG|DP] 사칙연산

0. 문제
사칙연산
1. 문제 풀이
백준의 행렬 곱셈 순서 문제와 유사한 문제이다.
처음에는 Greedy라고 생각하였다 . 하지만 DP! - 뒤에는 작은 수가, + 뒤에는 큰 수가 나와야 한다. 또한 순차적인 계산 방식이 아니므로 Greedy로 풀 수 없고, 행렬 곱셈 순서 문제처럼 step별로 계산하며 DP table로 상태를 계속 적어두어야 한다.

INF = 987654321
def solution(arr):
    answer=0
    num = (len(arr)+1)//2
    DP_max = [[-INF] *(num+1) for _ in range(num+1)]
    DP_min = [[INF] * (num+1) for _ in range(num+1)]
    for i in range(num):
        DP_max[i][i]=int(arr[2*i])
        DP_min[i][i]=int(arr[2*i])
    for i in range(num): #여기는 step
        for j in range(num-i): #여기는 step을 제공할 첫 index
            if i==1:
                DP_max[j][j+1] = eval(''.join(arr[2*j:2*j+3]))
                DP_min[j][j+1] = eval(''.join(arr[2*j:2*j+3]))
            else:
                for k in range(j,j+i):
                    if arr[2*k+1]=='-':
                        # print(j,j+i,k, '-')
                        DP_max[j][j+i]=max(DP_max[j][j+i], DP_max[j][k]-DP_min[k+1][j+i])
                        DP_min[j][j+i]=min(DP_min[j][j+i], DP_min[j][k]-DP_max[k+1][j+i])
                    else: #+라면
                        # print(j,j+i,k, '+')
                        DP_max[j][j+i]=max(DP_max[j][j+i], DP_max[j][k]+DP_max[k+1][j+i])
                        DP_min[j][j+i]=min(DP_min[j][j+i], DP_min[j][k]+DP_min[k+1][j+i])
    # print(DP_max)
    # print(DP_min)
    answer = DP_max[0][num-1]
    return answer

["1", "-", "3", "+", "5", "-", "8"] 위와 같은 수식이 존재한다면 일단
아래와 같은 DB 표를 max_dp, min_dp로 두 개 만들어준다. 우선 아무 계산도 하지 않았으므로 해당 index에 맞는 숫자로 초기화해준다.

index	0	1	2	3
0	1
1		3
2			5
3				8

이후 해당 표를 이용해 step 당 한 개씩 min_dp와 max_dp에 값을 갱신해준다. 여기에서 step이란 계산(덧셈, 뺄셈)의 갯수이다. 1+2는 step1 , 1+2-3 은 step2에 해당한다.

차례대로 step마다 계산해주는 와중에, 기호가 '+'가 나온다면 max_dp는 뒤를 max_dp의 값들로 갱신시키고, min_dp는 min_dp의 값들로 갱신시킨다. 반대로 기호가 '-'가 나오면 max_dp는 뒤를 min_dp 값들로, min_dp는 뒤를 max_dp 값들로 갱신시킨다.
예를 들어 0~3만큼의 계산은 0~1만큼의 계산 +(또는 -) 1~3만큼의 계산 과 0~2만큼의 계산 +(또는 -) 2~3만큼의 계산으로 할당할 수 있다.

index (max_dp)	0	1	2	3
0	1	-2(1-3)	3	1
1		3	8(3+5)	0
2			5	-3
3				8

index (min_dp)	0	1	2	3
0	1	-2(1-3)	-7	-15
1		3	8(3+5)	0
2			5	-3
3				8

위의 수식을 따라서 max와 min을 차례대로 한 번 계산해가다보면 위와 같은 형태가 나와야 한다.

이후 당연히 반환값은 DP_max[0][num-1] 이다.