사칙연산 1843

문제

접근 방법

1 - 5 - 3을 예시로 주었다.
((1 - 5) - 3) = -7
(1 - (5 - 3)) = -1
-5, -3으로 볼 수 있지만 -(5-3)을 통해 -2가 될 수 있다라는 것을 보여 주었다.

1 - 3 + 5 - 8을 예시로 주었다.
(((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

1-3은 -2가 된다.
3+5는 8이 된다.
(1 - 3) + 5은 6이 됐다.
1 - (3 + 5)을 통해 -7이 됐다.
예를 통해 알 수 있는 건 앞 숫자에 -가 붙으면 2가지 값으로 나뉘는데 큰 값이 다시 -를 붙어서 작은 값이 될 수도 있다는 것이다.

	1	-3	+5	-8
1	1	-2
-3		-3	2,-8
+5			+5	-3
-8				-8

2개씩 확인해본다.
[0][1]=[0][0]+[1][1]
[1][2]=[1][1]+[2][2]
[2][3]=[2][2]+[3][3]

	1	-3	+5	-8
1	1	-2	3,-7
-3		-3	2,-8	-6,0
+5			+5	-3
-8				-8

1개와 2개씩 확인한 것을 확인해본다.
[0][2]=[0][0]+[1][2] or [0][1]+[2][2]
3, -7 or 3, 3 = 3, -7
[1][3]=[1][1]+[2][3] or [1][2]+[3][3]
-6, -6 or -6, 0 = -6, 0

	1	-3	+5	-8
1	1	-2	3,-7	1,-15
-3		-3	2,-8	-6,0
+5			+5	-3
-8				-8

[0][3]=[0][0]+[1][3] or [0][2]+[3][3] or [0][1]+[2][3]
-5, 1 or -15, +1 or -5, -5= 1, -15
최대 최소만을 저장해주면 된다고 생각했다. (사이의 값보단 큰 영향을 주는 값들이기에 그렇다)
[0][3]=[0][0]+[1][3] or [0][2]+[3][3] or [0][1]+[2][3]를 순서대로 나열하면

[0][3]= [0][0]+[1][3], [0][1]+[2][3], [0][2]+[3][3]

식으로 나타내보면
x+3=y인 경우
[x][y]=[x][x]+[x+1][y],[x][x+1]+[x+2][y],[x][x+2][x+3][y]인 것이다.
즉 [x][y]=[x][x~x+2]+[x+1~x+3][y]이다.
이것을 활용하여 반복문을 작성하면 된다.

코드

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int maxDp[102][102], minDp[102][102];
int solution(vector<string> arr)
{
    int len = 0;
    bool minus = false;
    int num;
    for (string s : arr)
    {
        if (s == "-")
        {
            minDp[len][len] = num;
            maxDp[len][len++] = num;
            minus = true;
        }
        else if (s == "+")
        {
            minDp[len][len] = num;
            maxDp[len][len++] = num;
        }
        else
        {
            num = stoi(s);
            if (minus)
            {
                num *= -1;
                minus = false;
            }
        }
    }
    minDp[len][len] = num;
    maxDp[len][len++] = num;
    for (int i = 1; i < len; ++i) // 범위
    {
        for (int j = 0; j < len - i; ++j) // 위치
        {
            int minVal = 1000001, maxVal = -1000001;
            for (int k = 0; k < i; ++k) // 위치의 범위
            {
                if (k == 0 && minDp[j][j + k] < 0)
                {
                    int minM = minDp[j][j + k] - minDp[j + k + 1][j + i];
                    int minMaxM = minDp[j][j + k] - maxDp[j + k + 1][j + i];
                    minVal = min(minM, minVal);
                    maxVal = max(minM, maxVal);
                    minVal = min(minMaxM, minVal);
                    maxVal = max(minMaxM, maxVal);
                }
                if (k == 0 && maxDp[j][j + k] < 0)
                {
                    int maxM = maxDp[j][j + k] - maxDp[j + k + 1][j + i];
                    int maxMinM = maxDp[j][j + k] - minDp[j + k + 1][j + i];
                    minVal = min(maxM, minVal);
                    maxVal = max(maxM, maxVal);
                    minVal = min(maxMinM, minVal);
                    maxVal = max(maxMinM, maxVal);
                }
                int minP = minDp[j][j + k] + minDp[j + k + 1][j + i];
                int maxP = maxDp[j][j + k] + maxDp[j + k + 1][j + i];
                minVal = min(minP, minVal);
                maxVal = max(maxP, maxVal);
            }
            minDp[j][j + i] = minVal;
            maxDp[j][j + i] = maxVal;
        }
    }
    return maxDp[0][len - 1];
}

풀이

풀다가 햇깔려서 줄일 생각을 못했다.

["5", "-", "3", "+", "1", "+", "2", "-", "4"]

입출력 2번 예에서 문제가 발생했었는데 3이 아닌 5가 나온 것이다. 계산해보니 -3+1+2-4를 -2-2로 변환한 뒤 -(2-2)의 형태로 만들어 0이 되고 앞에 남아있는 5로 인해 최댓값이 나오는 것이었다. 하지만 처음 식에서 괄호로 나누어줄 수 없는 경우의 계산식으로 해결되어서는 안 되는 것이다.

해결법을 찾다가 다른 블로그를 보고 알게 됐다.
범위의 시작인 부분만 마이너스로 묶어주면 되는 것이다. 그렇게 되면 괄호로 묶을 수 있는 경우만 마이너스로 묶는 경우가 나오는 것이다. (범위의 시작이 아니면 이미 혼합된 값일 것이다. 그러한 값을 마이너스로 묶어주면 문제에서 의도한 바와 다른 값이 나온다)