사칙연산 / C++

https://school.programmers.co.kr/learn/courses/30/lessons/1843

프로그래머스

 

처음에는 주어진 숫자와 부호를 똑같이 취급했다.

ex. 1 + (-3) = -2

ex. -3 + 5 = -(3 + 5) = -8

dp[i][j] 에서 색상 라인으로 뻗어나간 두 노드를 탐색해 더 큰 수만 저장하는 방식으로 생각했는데, 오답이 너무 많이 나왔다.

중간중간 오류를 보완하는 코드를 넣었지만 반례가 너무 많아 접근 방식이 틀렸다고 인정하고 아이디어를 바꿨다.

위에서는 구간의 최댓값만 사용한다. 하지만 부호가 음수일경우, 구간 - 구간 일 경우에는 뒷 구간은 최솟값이어야 최대값이 출력된다.

 

부호가 양수

최대값: 최대 + 최대

최소값: 최소 + 최소

 

부호가 음수

최대값: 최대값 - 최소값

최소값: 최소값 - 최대값

 

미리 저장해놓은 dp[][] 배열에서 좌측 구간과 우측 구간 연산시 해당 연산자의 부호에 따라 점화식이 바뀐다.

이해하기 쉽게 이미지를 만들었다.

 

i가 의미하는것은 계산할 총 구간의 길이

s가 의미하는것은 구간의 시작 노드

그렇다면 구간의 끝 노드는 s + i - 1 이 될것이다.

 

1 - 1 - 1 + 5 - 1

에서 i = 2, s = 2 라면 e = 3 이다. 1 + 5 구간.

그렇다면 연산자 o의 위치는 2번 밖에 없다. [2] 1, [3] 5 사이에는 + 밖에 없으니까.

o = 2 >> (1) + (5) >> dp[2][2] 와 dp[3][3] 을 계산.

위 이미지를 보면 최대값 6, 최소값 6

 

i = 3, s = 0 이라면 e = 2 다. 0, 1, 2 번 노드를 계산한다. 1 - 1 - 1 구간.

o = 0 >> 1 - (1 - 1)  >> dp[0][0] 와 dp[1][2] 을 계산.

o = 1 >> (1 - 1) - 1  >> dp[0][1] 와 dp[2][2] 을 계산.

이때 부호는 음수니까 위에서 말한대로 최대값과 최소값을 구해주면 된다.

 

그렇게 끝까지 계산해주고 최대값을 리턴하면 끝.

 

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

pair<int, int> dp[205][205];
int is[205];
int solution(vector<string> arr)
{
    int size = arr.size() / 2 + 1;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            dp[i][j].first = -1e9;
            dp[i][j].second = 1e9;
        }
    }

    for (int i = 0; i < size; i++)
    {
        dp[i][i].first = stoi(arr[i * 2]);
        dp[i][i].second = stoi(arr[i * 2]);
    }
    for (int i = 0; i < size - 1; i++)
    {
        if (arr[i * 2 + 1] == "-")
        {
            is[i] = true;
        }
    }

    for (int i = 2; i <= size; i++) //사이즈
    {
        for (int s = 0; s + i - 1 < size; s++)
        {
            for (int o = s; o < s + i - 1; o++)
            {
                //cout << "start: " << s << ", end: " << s + i - 1 << ", operator: " << o << endl;
                if (is[o])
                {
                    dp[s][s + i - 1].first = max(dp[s][s + i - 1].first, dp[s][o].first - dp[o + 1][s + i - 1].second);
                    dp[s][s + i - 1].second = min(dp[s][s + i - 1].second, dp[s][o].second - dp[o + 1][s + i - 1].first);
                }
                else
                {
                    dp[s][s + i - 1].first = max(dp[s][s + i - 1].first, dp[s][o].first + dp[o + 1][s + i - 1].first);
                    dp[s][s + i - 1].second = min(dp[s][s + i - 1].second, dp[s][o].second + dp[o + 1][s + i - 1].second);
                }
            }
        }
    }


    return dp[0][size - 1].first;
}