백준 : 14888

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

14888번: 연산자 끼워넣기

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>

using namespace std;
int N;
int A[101];
char Ope_c[4] = { '+','-','*','/' };
int Ope[4] = { 0, };
int Max = -987654321;
int Min = 987654321;
void DFS(vector<int> cur,vector<char> v) {
	if (v.size() == N - 1) {
		int ans = A[0];
		for (int i = 0;i < N - 1;i++) {
			if (v[i] == '+') {
				ans += A[i + 1];
			}
			else if (v[i] == '-') {
				ans -= A[i + 1];
			}
			else if (v[i] == '*') {
				ans *= A[i + 1];
			}
			else {
				ans /= A[i + 1];
			}
		}

		Max = max(Max, ans);
		Min = min(Min, ans);
	}
	else {
		for (int i = 0;i < 4;i++) {
			if (Ope[i] > cur[i]) {
				cur[i]++;
				v.push_back(Ope_c[i]);
				DFS(cur, v);
				v.pop_back();
				cur[i]--;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);

	cin >> N;
	for (int i = 0;i < N;i++) cin >> A[i];

	for (int i = 0;i < 4;i++) cin >> Ope[i];


	vector<char> v;
	vector<int> cur(4, 0);

	DFS(cur, v);

	cout << Max << endl;
	cout << Min << endl;
}