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

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

[ 문제 바로가기 ]

< 16638번 문제인 괄호추가하기2 문제가 아닙니다. 괄호추가하기1(16637)문제의 2번째 방법 글입니다 ! >

괄호추가하기 (1) 글에서와는 다른 방법으로 문제를 해결하는 방법을 알아보자.

이전 글에서는, 문제를 해결하기에는 충분한 구현방법이었지만, 괄호추가하기2 라는 문제에 응용하기 어려운 부분이 있어서

이전 글과는 달리 정말로 괄호를 추가하고 안하고를 체크해가면서 완전탐색을 진행하는 방법을 알아보자.

[ 문제풀이 ]

1) 본인이 구현한 방법은 실제로 괄호를 친 곳을 따로 체크해주고, 계산을 진행하며, 괄호를 칠 수 있는 모든 곳에 쳐보는

   완전탐색 방법이다. 이전에 말했던 방식과 동일하게 재귀를 사용했지만, 조금 다른 방식의 완전탐색이다.

   이 전글과는 달리, 이 풀이법에서는 문자열을 한번에 입력받았다. 문자열을 한번에 입력받게되면, 숫자는 0번부터 짝수번에,

   연산기호는 홀수번 인덱스에 위치하게된다. (1 + 2 + 3 에서 1, 2, 3는 0, 2, 4번 인덱스, +, +는 1, 3번 인덱스)

   문제에서 괄호 연산자는 하나만 존재해야 한다고 했다. 또한, 괄호는 숫자에만 추가할 수 있다.

   1 ( + 2 ) + 3 같은 식은 애초에 말이 안되는 괄호 추가법이다. 즉, 우리는 하나의 숫자에 괄호를 추가하려면 + 2칸 뒤에 있는 숫자

   에도 괄호를 추가해줘야만 한다. 예를 들어서 1 + 2 * 3 + 4라는 식에서, 제일 앞에 숫자인 1에 괄호를 추가하는 방법으로는

   (1 + 2) * 3 + 4 라는 방법밖에 없기 때문이다. (1 + 2 * 3) + 4 혹은, (1) + 2 * 3 + 4와 같은 식은 문제의 조건에 맞지 않게된다.

   그렇다면 마지막 4라는 숫자에는 괄호를 어떻게 추가할까?? 물론, 1 + 2 * (3 + 4) 라는 식은 가능하지만, 본인이 말한것은

   1 + 2 * 3 + (4 이런식으로 괄호를 추가하는 경우를 말한것이다. 너무도 당연한거지만 추가를 할 수가 없다.

   또한 (1 + ( 2 ) * 3 )+ 4 와 같은 식도 성립할 수 없다. 구체적인 이야기는 아래쪽에서 다시 하자.

  

2) 본격적으로 괄호를 추가해보자 ! 본인은 먼저 괄호를 추가했는지 아닌지를 판단하기 위해서 GwalHo[] 라는 1차원 bool형 배열을

   사용하였다. GwalHo[a] = true의 의미는 a번인덱스에 괄호가 추가되있습니다 를 의미한다. 즉, 괄호가 추가되있으므로 더이상의

   괄호를 추가할 수 없다라는 것을 의미한다. 또한, 괄호는 세트로 존재하기 때문에(열기, 닫기) GwalHo[a] 가 true라면 자연스럽게

   GwalHo[a + 2]의 값도 true가 되도록 설정해 주어야 한다. 절대로 괄호는 연산자에 존재할 수 없기 때문에, GwalHo[a+1] 이 true

   가 아닌, GwalHo[a + 2]의 값인 true가 된다는 점 헷갈리지 말자.

   즉, 핵심은 괄호를 추가할때마다, 현재 인덱스번호 + 2씩 증가한다는 것이다. 여기서 하나의 조건을 우리는 더 파악할 수 있다.

   현재 인덱스번호 + 2가 N보다 작을 때만, 괄호를 추가할 수 있다는 것이다.

   1)에서 마지막에 가볍게 이야기했던, 1 + 2 * 3 + 4 에서 1 + 2 * 3 + (4 로 괄호를 추가할 수 없는 이유가 여기에 있다.

   1 + 2 * 3 + 4의 N값은 7이고, 4는 6번 인덱스이다. 6 + 2 = 8이 되버리고, 이는 인덱스의 범위를 벗어나버린 값이기 때문에 추가할

   수 없다. 그렇다면 지금까지 한 이야기와 앞으로 할 이야기에 대해서 깔끔하게 정리한번 하고 진행하자.

   < 지금까지 우리가 알아낸 내용 >

   1. 재귀를 이용해서 구현한다.

   2. GwalHo라는 배열을 이용해서, 실제로 괄호를 추가하고 안하고를 true / false로 표시를 한다.

      2.1) 괄호는 숫자에만 추가할 수 있으므로, 인덱스의 번호를 + 2씩 추가해주면서 세트로 관리해주어야 한다.

   3. 현재 숫자에, 괄호를 치기 위해서는 현재 인덱스번호에 +2를 한 값이 N보다는 작아야 한다.

   < 앞으로 우리가 알아낼 내용 >

   1. 지금까지 우리가 알아낸 내용의 3번의 조건에 위배되는 경우는? 즉, 현재인덱스번호 + 2가 N보다 큰 경우 어떻게?

   2. 괄호는 뭐 어떻게 계속 치고있는데 재귀의 종료는 언제?

   3. 실제적인 계산은 어떻게 ? 언제 ?

   

3) 앞으로 우리가 알아낼 내용의 순서에 맞게 진행해보자. 먼저 1번. 현재 인덱스번호 + 2 가 N보다 큰 경우는 어떻게 해야할까??

   먼저 생각을 해보자. 현재 인덱스번호 + 2가 N보다 크다는게 무엇을 의미하는 말일까??

   나는 현재 인덱스에 있는 숫자에다가 괄호를 치고싶은데, +2한 값인 N보다 커서 추가를 못한다 ! 과연 이게 무슨 말일까?

   결과부터 말하자면, 식의 마지막 숫자임을 의미한다. 마지막 숫자를 제외한 나머지 숫자들은 저 조건을 모두 만족하게 된다.

   1 + 2 * 3 + 4 가 있다. 첫번째 숫자인 '1'의 경우, +2를 해도, 식에 존재하는 인덱스범위로 갈 수 있다.

   '2'도 '3'도 +2씩 해보면, 식에 존재하는 인덱스 범위 내에서 해결이 가능하다. 유일하게 '4'만 , 즉 식의 마지막에 존재하는 숫자만

   + 2를 하게되면, 식의 범위를 벗어나 버리게 되는 것이다.

   여기서 우리는 재귀의 종료조건을 알아낼 수 있다. 현재 인덱스에 + 2를 한 값이 N보다 작다면, 계속 괄호를 추가하는 작업을

   진행하면 되지만, 그게 아니라면 식의 마지막 숫자까지 왔다는 것을 의미하고, 이제는 계산을 해야된다 라는 것을 알 수있다.

   실제 코드에 빗대어서 말해보자면, 현재 인덱스 + 2가 N보다 작을 경우에는, 인덱스번호를 +2씩하면서 괄호를 추가하기위해서

   재귀를 호출했지만, 그게 아닌 경우에는 현재 인덱스번호 + 1을 함으로써, 인덱스의 값을 N으로 만들어주었다.

   (식의 인덱스 범위는 0 ~ N-1). 즉, Index값이 N이되는 순간 계산을 진행하였다.

   이 부분을 코드로 보고 이해하고 넘어가보도록 하자.

void DFS(int Idx)         
{
    if (Idx >= N)                            // Idx의 값이 마지막 숫자를 넘어섰다면 = 종료조건
    {
        Answer = Bigger(Answer, Calculate()); // 계산하기 !
        return;
    }

    for (int i = Idx; i < N; i = i + 2)    // 현재 인덱스에서 반복문 시작. i의 값은 +2씩 증가 !
    {
        if (i + 2 < N)                // 현재 인덱스 + 2가 식의 인덱스 범위 내에 있는 값이라면 괄호 추가 가능 !
        {

           // 이미 괄호가 추가된 숫자들에 대해서는 중복된 괄호를 추가할 수가 없음.

           // 1 + 2 - 3 에서 +에 괄호를 추가하기 위해서는, 1과 2에 괄호가 없어야함 !

           // 즉, 현재 인덱스의 번호에 괄호가 없는지만 판단할 것이 아니라, +2칸 뒤에 있는 숫자에도 괄호가

           // 없어야만 괄호 추가 가능 !

           // 1 + (2 - 3) 에서, 1에는 괄호가 없지만, 2에는 괄호가 존재하므로 1에는 괄호를 추가할 수 없음 !
            if (GwalHo[i] == false && GwalHo[i + 2] == false)
            {
                GwalHo[i] = true;        // 괄호를 추가
                GwalHo[i + 2] = true;    // +2칸 뒤에도 마찬가지로 괄호를 추가
                DFS(Idx + 2);            // 재귀 호출 ! Idx + 2의 값으로 호출 !
                GwalHo[i] = false;       // 괄호를 없애고 다른 경우도 탐색
                GwalHo[i + 2] = false;    // +2칸 뒤에도 마찬가지로 괄호를 없앰
            }
        }
        else                        // 현재 인덱스 + 2가 식의 인덱스 범위 내에 존재하지 않음 = 마지막 숫자이면
        {
            DFS(i + 1);              // i + 1로, Idx값은 N으로 호출 !
        }
    }
}

     이로써 앞으로 해야할일에 1번과 2번이 동시에 해결이 되었다. 이제는 실제 계산하는 작업을 한번 해보도록 하자.

4) 우리가 계산할때의 우선순위는 괄호이다. 괄호를 무조건 먼저 계산해 주어야 한다.

   본인은 벡터를 먼저 하나 만들어주었다. 벡터가 관리하는 자료형은 string이며, 이 벡터에 식에 있는 모든 값들을 추가할 것인데,

   이 때 괄호안에 있는 값들은 계산 후에 추가해줄 것이다.

   즉, (1 + 2) * 3 + 4 라는 식이 있다면 벡터에는 "3" , "*" , "3" , "+", "4" 가 추가될 것이다.

   0부터 ~ N-1까지 반복을 하면서, 괄호가 있는 숫자라면, 계산을 먼저 해주고 vector에 push해준다.

   (1 + 2) * 3 + 4 에서 가장 먼저 1을 확인하는데, 괄호가 있는 숫자이기 때문에, 현재 인덱스의 값과, 현재 인덱스+2의 값을

   현재 인덱스 + 1의 기호로 계산을 해준다.

   1(0) +(1) 2(2) *(3) 3(4) + (5) 4(6)   ← 식으로 주어진 문자열의 각 문자와 인덱스번호. 문자(인덱스)

   즉, (1 + 2)를 한 3이라는 값을 문자열로 바꿔서 "3"으로 vector에 넣어준다.

   이 후, 1번 인덱스를 진행해야할까? 아니다. 이미 0, 1, 2번 인덱스들의 계산이 끝났다. 3번인덱스로 가야 제대로 된 계산이 가능

   하다. 즉, 괄호가 있는 숫자를 한번 계산했다면, 그 이후 판단할 인덱스의 번호는, 현재 인덱스 + 3이 된다.

   괄호가 없다면 그 문자를 그대로 vector에 넣어준다. 이 경우에는, 이후 판단 인덱스의 번호는 현재 인덱스 +1이 된다.

   (1 + 2) * 3 + 4 라는 식이 있었다면 vector에 { "3" , "*" , "3" , "+", "4" } 이렇게 값들이 존재할 것이다.

   바꿔서, 1 + (2 * 3) + 4라는 식이 있었다면 vector에 { "1", "+", "6", "+", "4" } 이렇게 값들이 존재할 것이다.

  

   이후 ,Vector를 홀수번호만 탐색하면서 계산을 진행해주면 된다. 실제로 해보면 알겠지만, 홀수번호만 탐색하는 이유는 무조건

   무조건 적으로 홀수번호에 연산기호가 있기 때문이다. Vector의 0번 인덱스의 값을 초기값으로, 연산기호에 맞는 연산을

   진행해주면 된다.

  

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
 
typedef long long ll;
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Oper_Num;
char MAP[MAX];
bool GwalHo[MAX];
ll Answer = -98765432198765;
 
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];
    }
    Oper_Num = N / 2;
}
 
ll Actual_Calc(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 (GwalHo[i] == false)
        {
            string S = "";
            S = S + MAP[i];
            V.push_back(S);
            i++;
        }
        else
        {
            string S = ""; S = S + MAP[i];
            ll Temp1 = stoi(S);
 
            S = ""; S = S + MAP[i + 2];
            ll Temp2 = stoi(S);
 
            S = ""; S = S + MAP[i + 1];
            string B_Temp = S;
 
            ll Temp_Result = Actual_Calc(Temp1, Temp2, B_Temp);
            V.push_back(to_string(Temp_Result));
            i = i + 3;
        }
    }
 
    ll R_Value = stoi(V[0]);
    for (int i = 1; i < V.size(); i = i + 2)
    {
        if (V[i] == "+")
        {
            R_Value = R_Value + stoi(V[i + 1]);
        }
        else if (V[i] == "-")
        {
            R_Value = R_Value - stoi(V[i + 1]);
        }
        else if (V[i] == "*")
        {
            R_Value = R_Value * stoi(V[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 (GwalHo[i] == false && GwalHo[i + 2] == false)
            {
                GwalHo[i] = true;
                GwalHo[i + 2] = true;
                DFS(Idx + 2);
                GwalHo[i] = false;
                GwalHo[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;
}