연산자 끼워넣기

문제 링크

연산자 숫자만 고려해서 이전 N과 M 시리즈에서 다뤘던 것 처럼 순열을 생성하고 마지막에 순열 대신 연산 결과의 최대값 / 최소값을 출력하는 문제이다. 각각의 연산자의 잔여 개수를 확인해가며 연산자 순열을 완성하고 최대값/최솟값을 갱신한다. 탐색이 완료되면 저장된 최댓값과 최솟값을 출력한다.

#include <isotream>
#include <vector>
#include <algorithm>
using namespace std;
int n; vector<int> arr, op;
int opc[4]; // 덧셈, 뺄셈, 곱셈, 나눗셈 순
int mx = -21e8;
int mn = 21e8;
void r(int p) {
	if(p == n) { // 연산자는 숫자 개수-1개
		int s = arr[1];
		for(int i=2;i<=n;i++) {
			switch(op[i - 1]) {
				case 1:
					s += arr[i];
					break;
				case 2:
					s -= arr[i];
					break;
				case 3:
					s *= arr[i];
					break;
				case 4:
					s /= arr[i];
					break;
			}
		}
		mx = mx > s ? mx : s;
		mn = mn < s ? mn : s;
		return;
	}
	for(int i=1;i<=4;i++) {
		if(opc[i - 1] == 0) continue; // 잔여 개수가 0이면 탐색 생략
		op[p] = i;
		opc[i - 1]--;
		r(p + 1);
		opc[i - 1]++;
	}
}
int main() {
	cin >> n; arr = op = vector<int>(n + 1);
	for(int i=1;i<=n;i++) {
		cin >> arr[i];
	}
	cin >> opc[0] >> opc[1] >> opc[2] >> opc[3];
	r(1);
	cout << mx << "\n" << mn;
	return 0;
}