[Algorithm]Baekjoon 16638번 :: 괄호 추가하기 2

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

 

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
int n;
string s;
vector<int> parenthesisIndex;
int answer = -2147483647;
 
struct Node
{
    int index;
    char op;
    int num;
};
 
int Calculate(int num1, char op, int num2)
{
    if (op == '+') return num1 + num2;
    if (op == '-') return num1 - num2;
    
    return num1 * num2;
}
 
bool IsNum(char num)
{
    if (num >= '0' && num <= '9') return true;
    return false;
}
 
bool cmp(const Node& a, const Node& b)
{
    return a.index < b.index;
}
 
void DFS(int index)
{
    if (index >= s.size() - 2) // 범위 벗어나면
    {
        string temp = s;
        vector<Node> nodes;
 
        for (int i = 0; i < parenthesisIndex.size(); ++i)
        {
            int index = parenthesisIndex[i];
            int num = Calculate(s[index] - '0', s[index + 1], s[index + 2] - '0');
 
            temp[index] = temp[index + 1] = temp[index + 2] = '.';
 
            nodes.push_back({ index,'#',num });
        }
 
        for (int i = 0; i < temp.size(); ++i)
        {
            if (temp[i] != '.')
            {
                if (IsNum(temp[i]))
                {
                    nodes.push_back({ i,'#',temp[i] - '0' });
                }
                else
                {
                    nodes.push_back({ i,temp[i], 0 });
                }
            }
        }
 
        sort(nodes.begin(), nodes.end(), cmp);
 
        // 곱셈만
        vector<Node> nodes2;
        
        for (int i = 0; i < nodes.size();)
        {
            if (nodes[i].op == '#') // 숫자면
            {
                nodes2.push_back(nodes[i]);
                ++i;
            }
            else if (nodes[i].op == '*')
            {
                int first = nodes2.back().num;
                nodes2.pop_back();
                
                int second = nodes[i + 1].num; // 반드시 숫자임.
                nodes2.push_back({ i,'#', first * second });
 
                i += 2;
            }
            else // 이외 더하기나 빼기 문자면
            {
                nodes2.push_back(nodes[i]);
                ++i;
            }
        }
 
        vector<Node> nodes3;
 
        for (int i = 0; i < nodes2.size();)
        {
            if (nodes2[i].op == '#')
            {
                nodes3.push_back(nodes2[i]);
                ++i;
            }
            else // 덧셈이나 뺄셈
            {
                int first = nodes3.back().num;
                nodes3.pop_back();
 
                int second = nodes2[i + 1].num; // 반드시 숫자임.
                nodes3.push_back({ i,'#', Calculate(first, nodes2[i].op, second) });
 
                i += 2;
            }
        }
 
        answer = max(answer, nodes3[0].num);
 
        return;
    }
 
    parenthesisIndex.push_back(index);
    DFS(index + 4);
    parenthesisIndex.pop_back();
    DFS(index + 2);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> s;
 
    if (s.size() == 1)
    {
        cout << s[0];
        return 0;
    }
 
    DFS(0);
 
    cout << answer;
}
 
 

 

태그는 백트래킹이다만... 거의 구현문제인 것 같다. 

괄호를 치는 경우의 수는 백트래킹으로 구하고, 이후 사칙연산을 구현해야 한다.

 

괄호치는 경우의수는 숫자를 기준으로 했다. 앞에서부터 괄호를 치나, 안치나의 선택지 2개로 분기점가르면서 모든 경우의 수를 구한다.

예를들어 0번째인덱스를 괄호쳤다는 표시를 했다면 (위 코드같은경우 parentHesisIndex라는 벡터에 0을 push_back),

인덱스에 +4해서 다음 탐색으로 넘어간다. 

왜 +4냐면,  괄호안에는 숫자 두개와 사칙연산기호 한개가있고 그다음에 또 사칙연산기호가 나오기 때문에, 괄호를 칠 수 있는 숫자로 넘어가려면 +4를 해줘야 한다.

 

ex) 3 + 8 * 7 - 9 * 2  가 있다고 가정. 

       앞에 숫자3은 0번째 인덱스. 만약 이 3부터 시작해서 +와 8을 포함해서 괄호를 친다면

      (3 + 8) * 7 - 9 * 2    가 된다. 그다음 괄호를 칠 수 있는 부분은 7이니까 7로 넘어가려면 +4를 해줘야 한다.

 

     문자 : 인덱스

      3     :    0

      +     :    1

      8     :    2

      *     :     3

      7     :    4          

 

괄호 안칠거면 그다음 숫자로 넘어가면 되니까 +2해주면 된다.

 

 

이렇게 괄호에 대한 경우의 수를 구한다음이 귀찮다. 숫자도 있고 문자도 있어서 나는 그냥 구조체를 하나 만들었다.

숫자도, 문자도(사칙연산 문자)도 담을 수 있는 구조체를 만들어서 좀 더 구현하기 편하게 했다.

 

먼저 괄호친것들에 대해서 계산 후, nodes에 넣고 나머지 계산해야할것들도 nodes에 넣는다.

node에는 index라는 변수가 있어서, 집어 넣을때 index만 잘 기록해주면 막 집어넣은 다음에 index기준 오름차순정렬 한번 해주면 계산순서가 보장된다.

 

그래서 먼저 맨처음 인풋값에서 괄호친거 먼저 계산해서 nodes에 넣어준 후, 나머지 괄호 안친것들을 전부 nodes에 넣어주고 정렬을 해준다.

 

그다음 사칙연산 우선순위상 곱셈을 먼저해야하니, nodes를 기준으로 곱셈식만 계산하고 nodes2에 넣어주고, 이후 계산안한것들도 nodes2에 전부 넣어주고 마찬가지로 인덱스기준 오름차순 정렬해준다.

 

이후 덧셈,뺄셈식도 마찬가지로 nodes3에다가 해주면, 최종적으로 nodes3[0] 이 계산식값이 된다.

이 계산식값을 계속 최대값으로 업데이트해주면 된다.

 

n값자체가 작아서, 계산식만 어떻게든 구현하면 딱히 시간초과 날 일은 없다.

개인적으로 이런 문제는 코테에서 안나왔으면 하는 바램이 있다..