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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 처음에는 N값이 최대 19이기 때문에, 모든 괄호를 다 씌워보는 완전탐색 방법을 고려해보았다. 모든 괄호를 다 씌워보더라도

   엄청나게 많은 경우를 탐색을 하는 것이 아니라고 생각했기 때문이다. 하지만 문제는 구현하는 법이었다. 주어진 식에서

   실제로 괄호를 씌우고 안씌우고를 어떻게 구현해야될지 몰라서 어차피 이 문제는 순서대로만 구현하면 되기 때문에 재귀를

   이용해서, 괄호를 씌우고 계속해서 계산하는 방법과 안씌우고 계산하는 방법 2가지를 이용해서 구현했다.

   본인은 이 글에서 이 문제를 해결하는 2가지 방법을 말하고자 한다. 첫 번째 방법은 위에서 말했듯이, 실제로 괄호를 어떻게

   씌워야 할지 몰라서 그냥 순차적으로 탐색하는 방법, 또 하나는 실제로 괄호를 씌우는 방법 !

   2가지 방법을 모두 말하는 이유는, 이 문제의 응용문제인 괄호 추가하기2 라는 문제가 있다. 괄호 추가하기2에서는 곱하기를

   우선적으로 먼저 계산해야 하는 조건이 붙어있는데, 이 경우에는 본인인 말한 전자의 풀이에서 응용하기가 너무 어려워서

   생각을 하다가 실제로 괄호를 추가하는 것처럼 표시하면서 탐색하는 방법을 한 가지 더를 구현해 보았기 때문이다.

  

2) 먼저 소개할 방법은 그냥 괄호를 추가하고 추가하지 않은 경우를 순차적으로 계산하는 방법이다.

   1)에서 말했듯이, 괄호를 추가하고 계산하는것과 추가하지 않고 계산하는 것을 어떻게 재귀를 이용해서 구현했는지 천천히

   알아보자.

   먼저, 본인은 숫자와 연산기호(+, -, *)을 따로 입력받았다. 그리고 재귀를 호출할때의 기준은 연산기호를 기준으로 잡았다.

   그렇다면 연산기호는 식에 몇개가 들어갈까?? 쉽게생각해보자. 1 + 2 + 3 이라는 식이 있다. 이 식의 길이는 5이기 때문에

   N = 5로 입력이 주어질 것이다. 연산자의 갯수는 2개 ! 즉, N / 2를 한 값이 연산기호의 갯수가 된다.

   갑자기 연산기호를 말한 이유는, 본인은 연산기호를 기준으로 잡았다고 했다. 즉, 깊이가 N / 2를 넘는다면 모든 연산기호에

   대한 계산이 끝난것이므로 더 이상 재귀를 진행하지 않는다는 것을, 즉 재귀의 종료조건을 말하기 위함이었다.
  

   1 + 2 * 3 이라는 식이 있다. 이 식에서는 괄호를 총 2곳에 만들 수 있다. (1 + 2) * 3 or 1 + (2 * 3) 이런식으로 !

   그렇다면, 여기서 중간에 있는 2의 값을 보자. 괄호를 어떻게 씌우냐에 따라서, 2는 계산되는 값? 방향? 이 달라지게 된다.

   연산기호 +를 기준으로 괄호를 씌운다면, (1 + 2)를 계산 후, 그 다음 연산기호인 *로 넘어가게 되는 것이고, 씌우지 않는다면

   (2 * 3)을 계산 후, 1 + 를 계산하고 그 다음으로 넘어가는 그런 방식인 것이다.

   이렇게 구현한 이유는, (1 + (2 * 3) ) 이라는 식이 가능하지 않기 때문이다. (괄호의 중복은 허용하지 않으므로)

  

   재귀 함수에 대한 매개변수만 잠깐 체크하고 다시 좀 더 구체적으로 알아보자. 본인은 재귀에 호출되는 매개변수를 2개 사용

   해 주었다. (int Idx , int Result). Idx에는 현재 연산기호의 위치를 나타내게 된다. 즉, 이 Idx값이 재귀의 깊이를 파악하는 변수로

   사용되며, 계산할때에도 사용되는 변수이다. Result에는 현재 계산된 결과값들을 호출하게 된다.

   초기에는 (0, Num[0]) 를 호출하고 재귀를 이어나가게 된다.

   다시 구체적으로 구현방법으로 넘어오자. 위의 식에서 연산기호를 하나 더 추가한 1 + 2 * 3 + 4 라는 식이 있다고 가정해보자.

   이 경우에, 첫번째 '+' 기호를 기준으로 괄호를 씌운다면, 다음 재귀 호출의 Result값에 (1 + 2)를 한 결과값인 3인 넘어가게 된다.

   Idx의 값은 그 다음 연산기호를 가르키기 위해서 Idx + 1 한 값이 넘어가게된다.

   그렇다면 +에 추가하지 않고, '*'에 추가한다고 생각해보자. 1 + (2 * 3) + 4 가 되는데, 이 문제는 앞에서부터 차례대로 계산한다고

   했으므로, 세 번째 연산자인 +를 계산할때의 식은 아마 7 + 4 가 될 것이다.

   즉, 괄호를 추가하지 않고, 그 다음 연산자에 괄호를 추가하게 되면, 연산기호를 가르키는 Idx변수가 2칸을 넘어가게 된다.

   쉽게 다시 말하자면, 1 + (2 * 3) + 4를 계산할 때, 처음 '+' 기호에 괄호를 씌우지 않을거면, 그 다음 연산자를 기준으로 괄호를

   씌우고 한번에 계산을 한 후에, 넘어가는 방식인 것이다. 이렇게 하는 이유는, 저 위에서 말했듯이, 1 + 2 * 3 이라는 식에서

   괄호를 어떻게 추가하냐에 따라 2가 계산되는 방향이 틀려지게 되기 때문이다.

   실제 구현된 코드를 한번 보면서 마지막으로 정리를 해보자.

void DFS(int Idx, int Result)    // 연산기호의 번호를 나타내는 Idx, 현재까지의 결과값인 Result
{
    if (Idx >= Oper_Num)
    {
        Answer = Bigger(Answer, Result);
        return;
    }

    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    // 현재 연산자를 기준으로 괄호를 추가하는 경우이다.
    int Cur_Result = Calculate(Result, Num[Idx + 1], Oper[Idx]);

    DFS(Idx + 1, Cur_Result);

    // 호출할 결과값 = 현재까지의 Result와, 연산자를 기준으로 오른쪽에 있는 값과 연산자에 따른 계산

    // 재귀를 호출하겠습니다.

    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    // 현재 연산자에 괄호를 추가하지 않고, 다음 연산자로 괄호를 추가하는 경우이다.

    if (Idx + 1 < Oper_Num)
    {
        int After_Result = Calculate(Num[Idx + 1], Num[Idx + 2], Oper[Idx + 1]);
        int Cur_Result = Calculate(Result, After_Result, Oper[Idx]);
        DFS(Idx + 2, Cur_Result);
    }

    // 현재 연산기호를 기준으로, 한 칸 더 넘어간 연산기호가 존재한다면

    // 한 칸 넘어간 연산기호부터 먼저 계산 후에, 그 결과값과 현재의 결과값을 현재 연산기호에 따른 계산 후

    // 재귀 호출.
    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

}

본인이 알려줄 첫 번째 방법은 이런식으로 구현을 해 보았다. (2)번 글에서는 실제로 괄호를 추가하고 말고를 표시하면서, 진행해

나가는 전체적인 풀이방법은 비슷하지만, 구현방식이 약간 다른 그런 방법을 알아보도록 하자 !

[ 소스코드 ]

#include<iostream>
#include<string>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Oper_Num;
int Answer = -987654321987654321;
int Num[MAX], Oper[MAX];
 
int Bigger(int A, int B) { return A > B ? A : B; }
 
void Input()
{
    cin >> N;
    int Idx = 0;
    int Idx2 = 0;
 
    string Inp;
    cin >> Inp;
    for (int i = 0; i < Inp.length(); i++)
    {
        if (i % 2 == 0) Num[Idx++] = Inp[i] - '0';
        else Oper[Idx2++] = Inp[i];
    }
    Oper_Num = N / 2;
}
 
int Calculate(int N1, int N2, char B)
{
    if (B == '+') return N1 + N2;
    else if (B == '-') return N1 - N2;
    else if (B == '*') return N1 * N2;
}
 
void DFS(int Idx, int Result)
{
    if (Idx >= Oper_Num)
    {
        Answer = Bigger(Answer, Result);
        return;
    }
 
    int Cur_Result = Calculate(Result, Num[Idx + 1], Oper[Idx]);
    DFS(Idx + 1, Cur_Result);
 
    if (Idx + 1 < Oper_Num)
    {
        int After_Result = Calculate(Num[Idx + 1], Num[Idx + 2], Oper[Idx + 1]);
        int Cur_Result = Calculate(Result, After_Result, Oper[Idx]);
        DFS(Idx + 2, Cur_Result);
    }
}
 
void Solution()
{
    if (N == 1)
    {
        cout << Num[0] << endl;
        return;
    }
    else if (N == 3)
    {
        cout << Calculate(Num[0], Num[1], Oper[0]) << endl;
        return;
    }
 
    DFS(0, Num[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;
}