백준 - 연산자 끼워넣기 (14888) [C++]

이 문제는 완전 탐색으로 풀었다.

 

최대 숫자의 개수가 11개이므로, 연산자의 개수는 최대 10개가 된다. 따라서 10개의 자리에 각 연산자를 집어넣으므로 10! 의 최대 수행 시간이 걸려 1초 안에 풀 수 있다.

 

로직은 매우 간단하다. 연산자를 N - 1개 선택하고, 모두 선택했을 때 계산을 진행해서 답을 구해주면 된다.

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

#define MAX 11
#define PLUS 0
#define MINUS 1
#define MUL 2
#define DIV 3
#define MAX_INIT -1000000001
#define MIN_INIT 1000000001

int N;
int A[MAX];
vector<int> oper;
vector<bool> visited;
int maxAnswer;
int minAnswer;

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < 4; i++) {
		int temp;
		cin >> temp;

		for (int j = 0; j < temp; j++) {
			oper.push_back(i);
		}
	}
}

void solve(vector<int> &tempOper) {
	if (tempOper.size() == N - 1) {
		int result = A[0];

		for (int i = 1; i < N; i++) {
			int presentOper = tempOper[i - 1];

			if (presentOper == PLUS) {
				result += A[i];
			} else if (presentOper == MINUS) {
				result -= A[i];
			} else if (presentOper == MUL) {
				result *= A[i];
			} else if (presentOper == DIV) {
				result /= A[i];
			}
		}

		maxAnswer = max(maxAnswer, result);
		minAnswer = min(minAnswer, result);

		return;
	}

	for (int i = 0; i < N - 1; i++) {
		if (!visited[i]) {
			visited[i] = true;
			tempOper.push_back(oper[i]);
			solve(tempOper);
			tempOper.pop_back();
			visited[i] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	input();
	visited = vector<bool>(N, false);
	maxAnswer = MAX_INIT;
	minAnswer = MIN_INIT;
	vector<int> tempOper;
	solve(tempOper);

	cout << maxAnswer << '\n';
	cout << minAnswer << '\n';

	return 0;
}