[찾아라 프로그래밍 마에스터] 사칙연산

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

코딩테스트 연습 - 사칙연산 | 프로그래머스

 

 

쉽지 않은 문제였다. 스택을 이용해서 풀려고 하니 답이 없어서 해설을 보았다. 동적계획법 문제는 항상, 동적계획법인 것을 알고나면 쉬워진다...

 

 

---

 

 

 

보통의 사칙연산 문제는 스택을 이용한 문제가 대부분이지만, 이 문제는 다르다.

 

 

 

 

+, -를 이용한 연산에서, 연산의 우선순위를 지정해 가장 최댓값을 구하는 것이다. 

 

 

 

 

작은 범위의 최댓값을 구해 놓으면, 더 큰 범위는 작은 범위를 이용해서 구할 수 있다.

 

 

 

 

a1 + a2 - a3 + a4 - a5 + a6 - a7 + a8을 생각해보면,

 

 

 

 

a1 ~ a8까지의 최댓값을 알기 위해서는,

 

 

 

ex) [a1 ~ a5] : a1부터 a5까지 연산의 최댓값

1. [a1] + [a2 ~ a8]

2. [a1 ~ a2] - [a3 ~ a8]

3. [a1 ~ a3] + [a4 ~ a8]

4. [a1 ~ a4] - [a5 ~ a8]

5. [a1 ~ a5] + [a6 ~ a8]

6. [a1 ~ a6] - [a7 ~ a8]

7. [a1 ~ a7] + [a8]

 

 

 

 

 

의 최댓값을 알아야한다. 그렇다면, 이 7개의 최댓값만 구해주면 되는 것일까에 대해서 의문이 될 수 있다.

 

 

 

 

 

7개 이외에 만들어질 수 있는 식은 없으므로, 7개만 구해주면 된다.

 

 

 

 

 

단, 연산도 있기 때문에, 최솟값도 찾아주면서 활용해야 한다.

 

 

 

 

---

 

 

해설코드(C++).

 

 

 

#include <vector>

#include <string>

#include <algorithm>

#include <iostream>

 

using namespace std;

 

int solution(vector<string> arr)

{

    int answer = 1;

    int dp[2][101][101] = { 0 };

    int check[101][101] = { 0 };

    for (int i = 0; i < arr.size(); i += 2) {

        dp[0][i][i] = atoi(arr.at(i).c_str());

        dp[1][i][i] = atoi(arr.at(i).c_str());

    }

 

    for (int c = 2; c <= arr.size() - 1; c += 2) {

        for (int i = 0; i < arr.size(); i += 2) {

            for (int j = i + 1; j <= i + c - 1; j += 2) {

                if (j >= arr.size())

                    break;

 

                if (arr.at(j) == "+") {

                    if (check[i][i + c] == 0) {

                        dp[0][i][i + c] = dp[0][i][j - 1] + dp[0][j + 1][i + c];

                        dp[1][i][i + c] = dp[1][i][j - 1] + dp[1][j + 1][i + c];

                        check[i][i + c] = 1;

                    }

                    else {

                        dp[0][i][i + c] = max(dp[0][i][i + c], dp[0][i][j - 1] + dp[0][j + 1][i + c]);

                        dp[1][i][i + c] = min(dp[1][i][i + c], dp[1][i][j - 1] + dp[1][j + 1][i + c]);

                    }

                }

                else {

                    if (check[i][i + c] == 0) {

                        dp[0][i][i + c] = dp[0][i][j - 1] - dp[1][j + 1][i + c];

                        dp[1][i][i + c] = dp[1][i][j - 1] - dp[0][j + 1][i + c];

                        check[i][i + c] = 1;

                    }

                    else {

                        dp[0][i][i + c] = max(dp[0][i][i + c], dp[0][i][j - 1] - dp[1][j + 1][i + c]);

                        dp[1][i][i + c] = min(dp[1][i][i + c], dp[1][i][j - 1] - dp[0][j + 1][i + c]);

                    }

                }

            }

        }

    }

 

    cout << dp[0][0][2] << endl;

    answer = dp[0][0][arr.size() - 1];

    return answer;

}