연산자 끼워넣기

 

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

 

C++

 

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

int n;
int a[12];
int op[11];
int maxResult = -2147000000;
int minResult = 2147000000;

void DFS(int depth,int result) {
	if (depth == n) {
		maxResult = max(maxResult, result);
		minResult = min(minResult, result);
	}
	else {
		if (op[1] != 0) {
			op[1]--;
			DFS(depth + 1,result+a[depth+1]);
			op[1]++;
		}
		if (op[2] != 0) {
			op[2]--;
			DFS(depth + 1,result-a[depth+1]);
			op[2]++;
		}
		if (op[3] != 0) {
			op[3]--;
			DFS(depth + 1,result*a[depth+1]);
			op[3]++;
		}
		if (op[4] != 0) {
			op[4]--;
			DFS(depth + 1,result/a[depth+1]);
			op[4]++;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= 4; i++) {
		cin >> op[i];
	}
	DFS(1,a[1]);
	cout << maxResult << "\n" << minResult << "\n";
	return 0;
}

 

#include <iostream>
#include <algorithm>

using namespace std;

int op[4];
int n;
int num[11];
int max_res = -2147000000;
int min_res = 2147000000;

void DFS(int res, int cnt) {
	if (cnt == n - 1) {
		max_res = max(max_res, res);
		min_res = min(min_res, res);
	}
	else {
		for (int i = 0; i < 4; i++) {
			if (op[i] > 0) {
				op[i]--;
				if (i == 0) DFS(res + num[cnt + 1], cnt + 1);
				else if (i == 1) DFS(res - num[cnt + 1], cnt + 1);
				else if (i == 2) DFS(res * num[cnt + 1], cnt + 1);
				else if (i == 3) DFS(res / num[cnt + 1], cnt + 1);
				op[i]++;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	for (int i = 0; i < 4; i++) cin >> op[i];
	DFS(num[0], 0);
	cout << max_res << "\n";
	cout << min_res << "\n";
	return 0;
}