[알고리즘] 백준 15658번: 연산자 끼워넣기 (2) (C++)

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

15658번: 연산자 끼워넣기 (2)

연산자 배열을 선언 후 각 연산자를 고른 경우 총 4가지를 가지고서 백트래킹 하면 된다.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int n;
vector<int> num;
int oper[4] = { 0, };
int maxValue = INT_MIN;
int minValue = INT_MAX;

void backTrack(int cnt, int sum) {
	if (cnt == n) {
		maxValue = max(maxValue, sum);
		minValue = min(minValue, sum);

		return;
	}

	for (int i = 0; i < 4; i++) {
		if (i == 0 && oper[i] > 0) {
			oper[i] -= 1;
			backTrack(cnt + 1, sum + num[cnt]);
			oper[i] += 1;
		}
		else if (i == 1 && oper[i] > 0) {
			oper[i] -= 1;
			backTrack(cnt + 1, sum - num[cnt]);
			oper[i] += 1;
		}
		else if (i == 2 && oper[i] > 0) {
			oper[i] -= 1;
			backTrack(cnt + 1, sum * num[cnt]);
			oper[i] += 1;
		}
		else if (i == 3 && oper[i] > 0) {
			oper[i] -= 1;
			backTrack(cnt + 1, sum / num[cnt]);
			oper[i] += 1;
		}
	}
}

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

	for (int i = 0; i < 4; i++) {
		cin >> oper[i];
	}

	backTrack(1, num[0]);

	cout << maxValue << '\n';
	cout << minValue;
	return 0;
}