알고리즘

  • 브루트포스로 함.
  • 서로 이웃한 정수끼리 연산을 하는 조합을 하는데, 모든 조합을 전부 다 돌린다.
    • 숫자는 최대 10개이고, 브루트포스로 했을때 O(n!) 이므로, 충분히 시간안에 돌릴 수 있다.

코드

#include <iostream>
using namespace std;
 
long long  N, num[10];
char op[10];
 
long long  calculate(int deep);
long long max(long long a, long long b) {
	return a > b ? a : b;
}
 
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		if (i % 2 == 0)
			cin >> num[i/2];
		else
			cin >> op[i/2];
	}
 
	cout << calculate(0);
}
 
long long  calculate(int deep) {
	if (deep == N / 2) {
		return num[0];
	}
 
	int last = (N - deep * 2) / 2;
	long long result = -6000000000;
	for (int i = 0; i < last; i++) {
		char saveOp = op[i];
		int saveNum = num[i], saveNum2 = num[i + 1];
 
		if (saveOp == '+')
			num[i] = saveNum + saveNum2;
		else if (saveOp == '-')
			num[i] = saveNum - saveNum2;
		else
			num[i] = saveNum * saveNum2;
 
		for (int j = i + 1; j < last; j++)
			num[j] = num[j + 1];
		for (int j = i; j < last - 1; j++)
			op[j] = op[j + 1];
 
		result = max(result, calculate(deep + 1));
 
		for (int j = last; j > i + 1; j--)
			num[j] = num[j - 1];
		for (int j = last - 1; j > i; j--)
			op[j] = op[j - 1];
		op[i] = saveOp;
		num[i] = saveNum;
		num[i + 1] = saveNum2;
	}
 
 
	return result;
}