15537 : 괄호 추가하기 - 재귀

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

문제요약

괄호를 추가하여 식의 최댓값 구하기

 

난이도

Gold 3

---

풀이 포인트

• 숫자와 기호 나누어 생각하기
• 재귀의 반복 동작 파악

---

REVIEW

 

우선 괄호를 친다는 것이 실제로 string 사이에 실물 괄호를 쳐주는 것이 아닌,

먼저 연산을 하면 된다는 것을 파악하고, stack에 쌓으며 pop을 해줄까 하는 아이디어를 떠올렸다.

 

다음으로는, string 수식을 어떻게 사칙연산으로 바꾸지 고민하다,

엄청나게 노가다로 calculate 함수를 구현했다.

 

그리고 괄호를 쳐줄 부분을 2중 for문을 돌려 고르고 substr해주는 식으로 재귀를 열심히 구현해봤다..

디버깅 코드가 콘솔창에 뜨는 것도 너무나 오래걸렸고 제출해보니 아니나 다를까 시간 초과.

 

재귀를 짤 때는 반복되는 동작을 구조화시키는 것이 핵심..

조합 재귀를 구현했듯이, 선택한다 안한다. 두가지 경우로 뻗어나간다고 생각하고 구조화해야 한다.

 

이 문제에서의 반복 동작은

3부분 ( 앞부분, 연산자, 뒷부분)으로 나누어 앞부분에 괄호를 친다, 뒷부분에 괄호를 친다로 나눌 줄 알아야 한다.

사실 이부분까지는 접근했는데 구현을 제대로 완성하지 못했다..

모범 코드 보며 다시 복습하기.

 

아직 수도코드로 구조를 대강 짜두고 세부화시키는 것에 능하지 않다.

생각나는대로 무조건 써보는 식이라 디버깅이 참 힘들다. 손코딩 연습해야겠다.

---

CODE

//완전 탐색을 할때는 idx 기반
// DAG : directed acyclic graph
// 완전탐색은 경우의 수가 거의 정해져있는 경우가 많다


#include <bits/stdc++.h>
using namespace std;

vector<int> num;
vector<char> oper_str;
int n, ret = -987654321;
string s;
void fastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int oper(char a, int b, int c)
{
    if (a == '+')
        return b + c;
    if (a == '-')
        return b - c;
    if (a == '*')
        return b * c;
}

void go(int here, int _num)
{
    //기저 사례
    if (here == num.size() - 1)
    {
        ret = max(ret, _num);
        return;
    }

    go(here + 1, oper(oper_str[here], _num, num[here + 1]));

    if (here + 2 <= num.size() - 1)
    {
        int temp = oper(oper_str[here + 1], num[here + 1], num[here + 2]);
        go(here + 2, oper(oper_str[here], _num, temp));
    }
    return;
}

int main()
{
    fastIO();

    cin >> n;
    cin >> s;

    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
            num.push_back(s[i] - '0');
        else
            oper_str.push_back(s[i]);
    }

    go(0, num[0]);

    cout << ret << "\n";
    return 0;
}

// 내가 구현한 수식 계산 노가다


int cal(string s)
{
    // *를 만나면 먼저 계산해서 그부분을 계산값으로 치환해주고 +,- 계산
    string pm = "";
    bool isfrontMul = false;

    for (int i = 0; i < s.size(); i++)
    {

        pm += s[i];
        // cout << "현재 pm에 쌓인 것은 " << pm <<'\n';

        if (s[i] == '*')
        {
            // cout << i << "번째 문자가 *이라서 곱해주겠다.\n";

            int a = s[i - 1] - '0';
            int b = s[i + 1] - '0';

            int k = a * b;
            // cout << "곱한 값은 " << k <<'\n';
            mul.push(k);

            pm = pm.substr(0, pm.size() - 2);
            // cout << "끝에 두글자를 빼면 " << pm <<'\n';

            pm += 'k';
            // cout << "곱한 값을 축적한 뒤 pm에  쌓인 것은 " << pm <<'\n';
            isfrontMul = true;
        }
        else
        {

            if (isfrontMul)
            {
                pm = pm.substr(0, pm.size() - 1);
                // cout << "이전이 곱셈 기호였기 때문에 끝자리 하나 빼면 " << pm << '\n';

                isfrontMul = false;
            }
        }
    }

    // cout << "곱셈 처리를 해준 뒤 식은 " << pm <<'\n';

    int ret = pm[0] - '0';

    if (pm[0] == 'k')
    {
        ret = mul.front();
        mul.pop();
    }

    // cout << "첫 숫자는 " << ret << '\n';

    int num = 1;

    for (int i = 2; i < pm.size(); i += 2)
    {

        if (pm[i] == 'k')
        {

            num = mul.front();
            // cout << i << "번째 숫자는 q에서 꺼내서" << num << '\n';
            mul.pop();
        }
        else
        {
            num = pm[i] - '0';
            // cout << i << "번째 숫자는 " << num << '\n';
        }

        if (pm[i - 1] == '-')
        {
            ret -= num;
            // cout << "- 기호를 만나서 결과값은 " << ret << '\n';
        }

        if (pm[i - 1] == '+')
        {
            ret += num;
            // cout << "+ 기호를 만나서 결과값은 " << ret << '\n';
        }
    }

    // cout << "최종 결과는 " << ret << '\n';
    return ret;
}