백준 16637번 괄호 추가하기 ( C++ )

문제

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

 

해설

조금 특수한 경우의 combi함수 사용

연산자 2개 안에서의 순서가 정해져있음

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n;
int ret = INT_MIN;
string line;
vector<int> num_list;
vector<char> oper_list;
 
int cal(int a, int b, char c)
{
  if (c == '+')
    return a + b;
  else if (c == '-')
    return a - b;
  else
    return a * b;
}
 
void combi(int i, int n)
{
  if (i == oper_list.size())
  {
    ret = max(n, ret);
    return;
  }
  combi(i + 1, cal(n, num_list[i + 1], oper_list[i]));
  if (i + 1 < oper_list.size())
    combi(i + 2, cal(n, cal(num_list[i + 1], num_list[i + 2], oper_list[i + 1]), oper_list[i]));
}
 
int main()
{
  cin >> n;
  cin >> line;
  for (int i = 0; i < line.size(); i++)
  {
    if (i % 2 == 0)
      num_list.push_back(line[i] - '0');
    else
      oper_list.push_back(line[i]);
  }
 
  combi(0, num_list[0]);
  cout << ret;
}