[ 백준 16638 ] 괄호 추가하기2 (C++)

백준의 괄호추가하기(16638) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 지난번 문제(괄호추가하기1) 에서 한 단계 더 응용된 괄호 추가하기2번 문제이다.

   [ 괄호추가하기1 문제 바로가기 ]

   [ 괄호추가하기1 풀이(1) 바로가기 ]

   [ 괄호추가하기1 풀이(2) 바로가기 ]

   이 문제는, 괄호추가하기1 에서 조건이 하나 더 추가되있다. 그 조건은 바로 곱하기를 더하기와 빼기보다 우선적으로 계산해

   주어야 한다는 것이다. 즉, 괄호를 중복적으로 추가시키거나, 괄호안에 2개이상의 연산기호는 들어갈 수 없다는 조건은

   같지만, 계산할 때 곱하기를 우선적으로 해 주어야 하는 것이다.

   결과적으로 보자면, 괄호를 추가하고 말고에 대한 구현방법은 괄호추가하기1 과 같은 방식으로 구현이 가능하다.

   다만, 계산하는 방식이 달라질 뿐이다. 그러므로, 본인은 이 글에서 괄호를 추가하는 방식에 대해서는 따로 설명을 하지 않을 것

   이다. 왜냐하면 위의 "괄호추가하기1 풀이(2)" 글을 링크를 타고 들어가서 읽어보면 괄호를 추가하는 방식에 대해서 설명이

   되어 있기 때문이다. 괄호추가하기1을 아직 해결하지 못한 사람이라면, 괄호추가하기1부터 해결을 하고 오도록하자.

   위에 링크를 클릭하면, 문제와 풀이과정을 모두 볼 수 있다.

  

2) 그렇다면 이제 계산하는 법에 대해서 생각해보기 전에, 괄호추가하기1 에서는 어떻게 계산을 했었는지 되짚고 넘어가보자.

   괄호추가하기1 에서는 괄호에 의해서 묶여있는 숫자들은, 먼저 계산을 하고 Vector에 push_back 하고, 그게 아닌 값들은

   그냥 바로 Vector에 push_back하는 방식이었다.

   괄호추가하기2에서도 여기까지는 똑같다. 괄호를 친 값들은 곱하기든 더하기든 빼기든 무조건 우선순위로 1등이기 때문에

   괄호를 친 놈들은 먼저 계산 후 Vector에 push해준다.

   그렇다면 이제부터 어떻게 해야될지 예를 보면서 이해해보자.

   1 + 2 * ( 3 + 4 ) 라는 식이 있다. 우리는 괄호에 있는 값들은 계산 후 Vector에 push해준다고 하였으니 현재 Vector의 상태는

   { "1" , " +" , "2" , "*" , "7" } 이 들어가 있을 것이다.

   여기서 우리는 곱하기를 먼저 계산할 것이기 때문에, 또 하나의 Vector를 더 생성해주어야한다.(본문 : vector<string> NV)

   동작 원리는 괄호에 있는 놈들을 먼저 계산한 것과 같다. 기존에 존재했던 Vector의 크기만큼 반복을 하는데,

   "*"연산이 아닌 다른 문자들에 대해서는 새로운 벡터인 NV에 그대로 push_back를 해주고, "*" 연산을 만나게 되면

   NV의 마지막 값과, "*" 연산 다음의 값을 *연산 후, NV의 마지막 값을 빼고 다시 NV에 넣어주면 된다.

   무슨 소린지 나조차도 모르겠다.

   기존에 괄호를 계산한 결과들을 모아둔 벡터에는 { "1" , " +" , "2" , "*" , "7" } 이 값들이 들어가 있다. 그렇다면, 위에서 말한대로

   "*" 가 아닌 문자들은 새로운 벡터인 NV에 그냥 넣어준다고 했으니 처음부터 차근차근 해보자.

   1 + 2 * 7 이 존재할 때, 우리가 생각하는 결과값은 15가 나와야한다. (2 * 7)을 먼저한 후에 1 + 를 진행하기 때문이다.

   "1"은 "*" 가 아니므로 NV에 그냥 넣어준다. 현재 NV = { "1" }

   "+"는 "*" 가 아니므로 NV에 그냥 넣어준다. 현재 NV = { "1" , "+" }

   "2"는 "*" 가 아니므로 NV에 그냥 넣어준다. 현재 NV = { "1" , "+", "2" }

   다음은 "*" 연산자이다. 즉, 우리는 "*" 를 기준으로 앞에 있는 숫자와 뒤에 있는 숫자를 x연산을 해야 하는 것이다.

   앞에 있는 숫자는 NV의 마지막 값인 "2" 가 될 것이고, 다음에 있는 숫자는 기존 벡터인 V의 현재 인덱스 + 1번 값이 될 것이다.

   기존 벡터 V에서 "*" 는 3번 인덱스에 위치해있다.

   즉, 우리는 "*" 연산자를 만나게 되면

   NV의 가장 마지막 값 = NV[NV.size() - 1] 과 V[현재Idx + 1]의 값을 곱하기 연산을 시켜주면 되는 것이다.

   이렇게 곱하기 연산을 했다고 치자. 그 이후에 NV에 곱한 값을 넣어준다면 어떻게 될까??

   NV에는 { "1" , "+" , "2" , "14" } 가 들어가 있을 것이다. 뭔가 이상한거 같다. 분명히 2는 계산을 했음에도 계속 존재하고 있다.

   우리는 "*" 연산자를 만나게 되면, NV의 마지막 값을 가져와서 곱하기 연산을 실행 한 후에, NV에서 가장 마지막 값을 제거해줘야

   한다. 즉, NV.pop_back() 이라는 명령을 실행해 주어야 한다는 것이다.

   그렇게 되면 NV는 { "1", "+", "14" } 로 우리가 원하는 식의 형태로 남을 것이다.

   지금부터는 또 괄호추가하기1과 같다. NV의 첫번째 값을 시작점으로 잡고, 중간에 나오는 연산자에 따라서 계산을 진행해주면

   우리가 원하는 결과를 얻을 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
 
typedef long long ll;
#define endl "\n"
#define MAX 20
using namespace std;
 
int N;
char MAP[MAX];
bool Gwal_Ho[MAX];
ll Answer = -987654321987654321;
 
ll Bigger(ll A, ll B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> MAP[i];
    }
}
 
ll Actual_Calculate(ll N1, ll N2, string B)
{
    if (B == "+") return N1 + N2;
    else if (B == "-") return N1 - N2;
    else if (B == "*") return N1 * N2;
}
 
ll Calculate()
{
    vector<string> V;
    for (int i = 0; i < N;)
    {
        if (Gwal_Ho[i] == false)
        {
            string S = "";
            S = MAP[i];
            V.push_back(S);
            i++;
        }
        else
        {
            string S = ""; S = S + MAP[i];
            ll Temp = stoi(S);
            
            S = "";
            S = S + MAP[i + 2];
            ll Temp2 = stoi(S);
 
            S = "";
            S = S + MAP[i + 1];
            string B_Temp = S;
 
            ll Temp_Ans = Actual_Calculate(Temp, Temp2, B_Temp);
            string S_Temp_Ans = to_string(Temp_Ans);
            V.push_back(S_Temp_Ans);
            i = i + 3;
        }
    }
 
    vector<string> NV;
    for (int i = 0; i < V.size(); )
    {
        if (V[i] == "*")    
        {
            ll Temp = stoi(NV[NV.size() - 1]);
            ll Temp2 = stoi(V[i + 1]);
            ll Temp_Ans = Actual_Calculate(Temp, Temp2, V[i]);
            string S_Temp_Ans = to_string(Temp_Ans);
            NV.pop_back();
            NV.push_back(S_Temp_Ans);
            i = i + 2;
        }
        else
        {
            NV.push_back(V[i]);
            i = i + 1;
        }
    }
    
    ll R_Value = (ll)(stoi(NV[0]));
    for (int i = 1; i < NV.size(); i = i + 2)
    {
        if (NV[i] == "+") R_Value = R_Value + stoi(NV[i + 1]);
        else if (NV[i] == "-") R_Value = R_Value - stoi(NV[i + 1]);
    }
 
    return R_Value;
}
 
void DFS(int Idx)
{
    if (Idx >= N)
    {
        Answer = Bigger(Answer, Calculate());
        return;
    }
 
    for (int i = Idx; i < N; i = i + 2)
    {
        if (i + 2 < N)
        {
            if (Gwal_Ho[i] == false && Gwal_Ho[i + 2] == false)
            {
                Gwal_Ho[i] = true;
                Gwal_Ho[i + 2] = true;
                DFS(Idx + 2);
                Gwal_Ho[i] = false;
                Gwal_Ho[i + 2] = false;
            }
        }
        else
        {
            DFS(i + 1);
        }
    }
}
 
void Solution()
{
    DFS(0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}