[프로그래머스] 사칙연산

문제 설명

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다. 예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

• ((1 - 5) - 3) = -7
• (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다. 또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

• (((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

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다. 문자열 형태의 숫자와, 더하기 기호(“+”), 뺄셈 기호(“-“)가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• arr는 두 연산자 “+”, “-“ 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.
• arr의 길이는 항상 홀수입니다.
• arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.
• 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : “456”)
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

---

풀이

60분 이상
예전에 풀었던 문제 중 비슷한 느낌의 dp문제의 기억을 떠올리며 풀이를 진행했는데, 제출하니 틀렸다. 최댓값을 구하는 문제이므로 dp배열에 (i번째 숫자부터 j번째 숫자까지 연산할 때의 최댓값)을 갱신했는데, 빼기 연산에서 최댓값의 경우의 수를 제대로 고려하지 못한 것이었다. 최댓값을 구할 때 연산이 덧셈이라면 (최댓값 + 최댓값)의 형태가 맞지만, 뺄셈이라면 (최댓값 - 최솟값)의 형태를 가져야하기 때문이다. 따라서 최댓값과 최솟값을 기록해두는 배열을 따로 선언하여 통과할 수 있었다.

코드

// 02:00 ~ 3:15
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int solution(vector<string> arr)
{
    int num_size = (arr.size() + 1)/2;
    int dp_max[101][101];
    int dp_min[101][101];
    
    for(int i = 0; i < arr.size(); i += 2){
        dp_max[i / 2][i / 2] = stoi(arr[i]);
        dp_min[i / 2][i / 2] = stoi(arr[i]);
    }

    for(int len = 1; len < num_size; ++len){
        for(int i = 0; i + len < num_size; ++i){
            int j = i + len;
            dp_max[i][j] = -1000000000;
            dp_min[i][j] = 1000000000;
            for(int k = 0; i + k < j; ++k){
                if(arr[(i + k)*2 + 1] == "-"){
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][i + k] - dp_min[i + k + 1][j]);
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][i + k] - dp_max[i + k + 1][j]);
                }
                else{
                    dp_max[i][j] = max(dp_max[i][j], dp_max[i][i + k] + dp_max[i + k + 1][j]);
                    dp_min[i][j] = min(dp_min[i][j], dp_min[i][i + k] + dp_min[i + k + 1][j]);
                }
            }
        }
    }
    
    return dp_max[0][num_size-1];
}