백준 14888번 연산자 끼워넣기(C++)

 삼성 역량 기출 문제를 모두 풀어보는 것이 이번학기 목표이다.
먼저 생각난 풀이는 트리를 구성한 후 dfs 하는 것이었다. 예를 들어 + - x 한개씩 들어왔다고 생각하고 트리를 구성해보면         

         +               x               -
        / \              / \              / \
     -     x          -    +         +     x
     |      |          |      |         |      |  
     x     -          +     -         x     +
 
이렇게 6가지 경우의 수가 나온다. 이렇게 트리를 구성하고 각 루트를 시작으로 dfs 하면 완전탐색을 할 수 있을 것이다. 그러나 트리를 구성하는것도 귀찮은 일이고 순서대로 트리를 계속 넣는 게 어려웠다.
그 다음 생각난 풀이가 순열이다. + - x 를 원소로 모든 수를 사용하는 순열을 만들어 완전탐색했다. 백트래킹을 이용한 순열의 대한 글은 아래를 참조하면 좋다.https://tigerfrom2.tistory.com/72
다만, 결과를 보면 시간이 매우 오래걸린 것을 알 수 있는데 이것은 다른 사람들의 코드와 비교해보니 다른 사람들은 벡터를 사용하지 않았고 난 벡터를 사용했기 때문이다. 로직은 같다.

DFS를 활용한 순열

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

vector<int> num;
vector<char> op;
vector<char> oper;

int max_ = INT_MIN;
int min_ = INT_MAX;
bool visited[11] = { false, };
int N;

void dfs(int cnt) {
	if (cnt == N - 1) {
		int sum = num[0];
		for (int i = 0; i < N - 1; i++) {
			if (oper[i] == '+')
				sum += num[i + 1];
			else if (oper[i] == '-')
				sum -= num[i + 1];
			else if (oper[i] == '*')
				sum *= num[i + 1];
			else if (oper[i] == '/')
				sum /= num[i + 1];
		}
		if (max_ < sum)
			max_ = sum;
		if (min_ > sum)
			min_ = sum;

		return;
	}
	for (int i = 0; i < N - 1; i++) {
		if (visited[i] == true)
			continue;
		visited[i] = true;
		oper.push_back(op[i]);
		dfs(cnt + 1);
		oper.pop_back();
		visited[i] = false;
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		num.push_back(tmp);
	}

	for (int i = 0; i < 4; i++) {
		int tmp;
		cin >> tmp;
		if (i == 0) for (int j = 0; j < tmp; j++) 	op.push_back('+');
		else if (i == 1) for (int j = 0; j < tmp; j++) 	op.push_back('-');
		else if (i == 2) for (int j = 0; j < tmp; j++) 	op.push_back('*');
		else if (i == 3) for (int j = 0; j < tmp; j++) 	op.push_back('/');
	}

	dfs(0);

	cout << max_ << '\n';
	cout << min_ << '\n';
}