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

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

처음에 DP로 풀까 고민을 하다가, 단순히 뒤에서 부터 최대 또는 최솟값을 유지하면서 계산하면 풀릴 것이란 생각이 들었다.

그래서 뒤에서 min max값 중 하나를 선택하면서 계산하도록 코드를 작성을 했는데, 안타깝게도 예외 케이스가 생겨 다시 DP로 풀기로 마음을 바꿨다.

 

DP로 풀 때 정말 헷갈렸던 것은 부호였다.

나는 2차원 vector를 이용해 a부터 b구간의 min값과 max값을 저장했다.

문제는 min값 일 때 부호가 -면 min값에 -1을 곱해서 사용해야하나? max값에 -1을 곱해야하나? 이런 이상한 의문이 들어벼렸기 때문이다.

다행히 문제를 풀다보니 그냥 앞에 부호가 -일 경우에는 두가지 경우로 나눠서 값만 저장해 주면 된다는 사실을 알았다.

 

예를 들어 (a, b)  (b+1, c) 구간의 min값을 구할 때 

 

1. (a, b)구간의 min값에서 (b+1, c) 구간의 max값을 뺀 값

2. (a, b)구간의 min값에서 (b+1, c) 구간의 min값을 더한 값

 

위 두 값중 어떤 값이 작은지 비교하고, 그 중 더 작은 값이 (a, c) 구간의 최솟값이 되는 것이다.

 

max도 마찬가지로 두가지 경우로 쪼개서 구하면 된다.

 

부호가 +일 경우는 단순히 계산하면 되기 때문에 특별한 경우가 없었다.

​

 

[아이디어 정리]

1. 2차원 vector를 2개 만든다. (vector_min[i][j]에서 i, j에는 i부터 j번째 숫자까지의 합이 최소인 값이 저장된다.)
2. (a, b) 구간의 최댓값이나 최솟값을 구할 때, for 문을 활용해 두개의 구간으로 쪼개고 각 구간의 최대 최솟값을 이용해 (a, b) 구간의 최대, 최솟값을 구한다
3. 최종적으로 구한 최대값을 return한다.

 

 

Code

 

 

#include <vector>
#include <string>
#include<algorithm>
using namespace std;

vector<vector<int>> minV;
vector<vector<int>> maxV;
vector<string> realArr;
vector<vector<bool>> MinCalc;
vector<vector<bool>> MaxCalc;


int DP(int st, int ed, bool isMax);

int calcDP(int st, int i, int ed, bool isMax)
{
    int a,b,c,d, rrr;
    a=DP(st,i,true); //max
    b=DP(st,i,false); //min
    c=DP(i+1,ed,true); //max
    d=DP(i+1,ed,false); //min
    if (isMax)
    {
        if (realArr[st*2-1]=="-")
        {
            rrr= max(b-d,a+c); //min-min를 하는 이유는 +가 있을 경우 -가 안되기 때문이다. max-min이 답일 경우는 다른 경우에서 어차피 저장해준다.
        }
        else
        {
            rrr= a+c;
        }
    } 
    else
    {
        if (realArr[st*2-1]=="-")
        {
            rrr= min(b-c,b+d);
        }
        else
        {
            rrr= b+d;
        }
    }
    return rrr;
}

int DP(int st, int ed, bool isMax)
{
    if (isMax)
    {
        if (MaxCalc[st][ed])
        {
            return maxV[st][ed];
        }
        else
        {
            for (int i=st; i<ed; i++)
            {
                maxV[st][ed]=max(maxV[st][ed],calcDP(st, i, ed,true));
                                
            }
            MaxCalc[st][ed]=true;
            return maxV[st][ed];
        }        
    }
    else 
    {
        if (MinCalc[st][ed])
        {
            return minV[st][ed];
        }
        else
        {
            for (int i=st; i<ed; i++)
            {
                minV[st][ed]=min(minV[st][ed],calcDP(st, i, ed, false));
            }
            MinCalc[st][ed]=true;
            return minV[st][ed];
        }   
    }
    
}

int solution(vector<string> arr)
{
    int arrN=(arr.size()/2)+1;
    realArr=arr;
    minV=vector<vector<int>>(arrN, vector<int>(arrN,5000000));
    maxV=vector<vector<int>>(arrN, vector<int>(arrN,-5000000));
    MinCalc=vector<vector<bool>>(arrN, vector<bool>(arrN,false));
    MaxCalc=vector<vector<bool>>(arrN, vector<bool>(arrN,false));
    for (int i=1; i<arrN; i++)
    {
        if (arr[2*i-1]=="-")
        {
            MinCalc[i][i]=true;
            MaxCalc[i][i]=true;
            minV[i][i]=-stoi(arr[2*i]);
            maxV[i][i]=-stoi(arr[2*i]);
        }
        else
        {
            minV[i][i]=stoi(arr[2*i]);
            MinCalc[i][i]=true;
            MaxCalc[i][i]=true;
            maxV[i][i]=stoi(arr[2*i]);
        }
    }
    DP(1, arrN-1,true);
   
    return stoi(arr[0])+maxV[1][arrN-1];
}

 

---

 

처음에 헷갈려서 잘못 풀었더니, 그 이후에 초기화도 실수하는 등 오류가 생겼다.

덕분에 코드가 많이 길어지게 됐다...

다음에는 더 잘 하자..?

 

프로그래머스