프로그래머스[Lv.4] - 최적의 행렬 곱셈

프로그래머스[Lv.3] - 최적의 행렬 곱셈

 

 

문제 설명

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 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")
• 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

---

 

 

 

 

 

 

풀이

어제 풀었던 프로그래머스[Lv.3] - 최적의 행렬 곱셈 문제와 거의 흡사하다.

다른 점은 연산 결과의 최댓값을 구한다는 점과 연산이 두 종류라는 점이다.

그렇다면 이전에 풀었던 방법을 응용하여 해결할 수 있을 것이다.

 

이전에는 DP를 이용하여 시작과 끝 지점을 정한 뒤, 그 중간을 하나씩 자르며 결과를 확인했다.

이번에도 같은 방법을 이용하면 된다.

하지만, 이 문제의 경우에는 연산이 "+", "-"로 두 종류이다.

문제의 목표는 최댓값을 만드는 것이니 "-"연산 뒤에는 가장 작은 값이 오는게오는 게 유리하고 "+"연산 뒤에는 가장 큰 값이 오는 게 유리하다.

즉, DP를 기록할 자료구조를 두 가지로 나눠서 관리해야 한다.

start부터 end까지 연산결과를 저장하되, 하나는 가장 작은 값을, 하나는 가장 큰 값을 관리하게 한다.

vector<vector<int>> dpMax((arr.size()+1)/2, vector<int>((arr.size()+1)/2, INT_MIN));
vector<vector<int>> dpMin((arr.size()+1)/2, vector<int>((arr.size()+1)/2, INT_MAX));

(arr의 절반을 쓰는 이유는 연산자를 숫자와 분리하였기 때문이다.)

 

이후, n개씩 연산하며 결과를 확인할 것이다.

이때, n개의 연산을 시작부터 끝 지점사이를 나누며 연산 결과를 기록하면 된다.

for(int i = 0; i < nums.size(); i++)
{
    for(int start = 0; start < nums.size(); start++)
    {
        int end = start+i;
        if(end >= nums.size()) break;

        for(int k = start; k < end; k++)
        {
            if(oper[k] == MINUS)
            {
                dpMin[start][end] = min(dpMin[start][end], dpMin[start][k] - dpMax[k+1][end]);
                dpMax[start][end] = max(dpMax[start][end], dpMax[start][k] - dpMin[k+1][end]);
            }
            else
            {
                dpMin[start][end] = min(dpMin[start][end], dpMin[start][k] + dpMin[k+1][end]);
                dpMax[start][end] = max(dpMax[start][end], dpMax[start][k] + dpMax[k+1][end]);
            }
        }
    }
}

 

이 과정이 끝나면 dpMax[0][nums.size()-1]에 0번부터 끝까지 연산한 결과 중 가장 큰 값이 기록되어 있을 것이다.

---

 

 

 

 

 

전체 코드

#include <vector>
#include <string>
#include <iostream>
#include <climits>
using namespace std;

enum
{
    MINUS,
    PLUS
};

int solution(vector<string> arr)
{
    int answer = -1;
    
    vector<vector<int>> dpMax((arr.size()+1)/2, vector<int>((arr.size()+1)/2, INT_MIN));
    vector<vector<int>> dpMin((arr.size()+1)/2, vector<int>((arr.size()+1)/2, INT_MAX));
    vector<int> nums;
    vector<int> oper;
    for(int i = 0 ; i < arr.size(); i++)
    {
        if(i%2 == 0)
        {
            int num = 0;
            for(auto c : arr[i])
            {
                num *= 10;
                num += c - '0';
            }
            
            nums.push_back(num);
        }
        else
        {
            if(arr[i] == "-") oper.push_back(MINUS);
            else oper.push_back(PLUS);
        }
    }

    for(int i = 0 ; i < nums.size(); i++) 
    {
        dpMax[i][i] = nums[i];
        dpMin[i][i] = nums[i];
    }
    
    for(int i = 0; i < nums.size(); i++)
    {
        for(int start = 0; start < nums.size(); start++)
        {
            int end = start+i;
            
            if(end >= nums.size()) break;
            
            for(int k = start; k < end; k++)
            {
                if(oper[k] == MINUS)
                {
                    dpMin[start][end] = min(dpMin[start][end], dpMin[start][k] - dpMax[k+1][end]);
                    dpMax[start][end] = max(dpMax[start][end], dpMax[start][k] - dpMin[k+1][end]);
                }
                else
                {
                    dpMin[start][end] = min(dpMin[start][end], dpMin[start][k] + dpMin[k+1][end]);
                    dpMax[start][end] = max(dpMax[start][end], dpMax[start][k] + dpMax[k+1][end]);
                }
            }
        }
    }
    
    return dpMax[0][nums.size()-1];
}

---