[BOJ] 백준 14888 연산자 끼워넣기

문제링크 : https://www.acmicpc.net/problem/14888

 이 문제는 브루트포스를 사용해서 모든 연산자의 경우의 수를 구하는 문제이다.

연산자 집합이 { +,+,-,*,/ } 이렇게 있을 경우, 이 연산자들을 나열할 수 있는 모든 경우의 수를 구해야 한다. 따라서 재귀함수를 사용한다.

주의해야 할 점은 + - + * / 와 + + - * / 은 엄연히 다른 나열이다. 따라서 한번 건들였던 연산자는 다시 건들지 않기 위해 bool 배열을 사용하여 visit 여부를 관리해 주어야 한다.

소스코드 :

#include <iostream>
#include <vector>
using namespace std;

long long * v;
vector<char> op;
vector<bool> op_flag;
int maxSize;

long long maxNum = -10000000001;
long long minNum = 10000000001;

long long Sum(vector<char> operators) {

 long long  * v_t = new long long[maxSize];

 for (int i = 0; i < maxSize; i++)
  v_t[i] = v[i];

 for (int i = 0; i < maxSize - 1; i++) {
  if (operators[i] == '+') {
   v_t[i + 1] = v_t[i] + v_t[i + 1];
  }
  else if (operators[i] == '-') {
   v_t[i + 1] = v_t[i] - v_t[i + 1];
  }
  else if (operators[i] == '/') {
   v_t[i + 1] = v_t[i] / v_t[i + 1];
  }
  else if (operators[i] == '*') {
   v_t[i + 1] = v_t[i] * v_t[i + 1];
  }
 }

 delete v_t;
 return v_t[maxSize - 1];
 
}



void Func(vector<char> v, int s) {
 if (maxSize == 1) {
  maxNum = ::v[0];
  minNum = ::v[0];
  return;
 }
 if (v.size() >= maxSize - 1) {
  long long res = Sum(v);
  if (maxNum < res) {
   maxNum = res;
  } 
  if (minNum > res) {
   minNum = res;
  }
  return;
 }

 for (int i = 0; i < maxSize - 1; i++) {
  if (op_flag[i] == false) {
   v.push_back(op[i]);
   op_flag[i] = true;
   Func(v, i + 1);
   op_flag[i] = false;
   v.pop_back();
  }
 }
}


int main() {
 cin >> maxSize;
 v = new long long[maxSize];
 for (int i = 0; i < maxSize; i++) {
  cin >> v[i];
 }
 for (int i = 0; i < 4; i++) {
  int tmp;
  cin >> tmp;
  switch (i) {
  case 0:
   for (int j = 0; j < tmp; j++) {
    op.push_back('+');
    op_flag.push_back(false);
   }
   break;
  case 1:
   for (int j = 0; j < tmp; j++) {
    op.push_back('-');
    op_flag.push_back(false);
   }
   break;
  case 2:
   for (int j = 0; j < tmp; j++) {
    op.push_back('*');
    op_flag.push_back(false);
   }
   break;
  case 3:
   for (int j = 0; j < tmp; j++) {
    op.push_back('/');
    op_flag.push_back(false);
   }
   break;
  }
 }
 
 vector<char> tmp;
 Func(tmp,0);
 cout << maxNum << endl << minNum << endl;
}