[BOJ] 14888 - 연산자 끼워넣기

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

---

[알고리즘풀이]

백트레킹 기법을 이용하여, 가능한 모든 경우에 대해서 수식을 만들어 계산을 해본다.

( 0 : + , 1 : - , 2 : * , 3 : / 를 의미 )

#include<iostream>
#include<vector>

using namespace std;

int ma = -1000000001, mi = 1000000001;

void bt(int, vector<int>, vector<int>, vector<int>);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> v(n), o(4), k;
	for (int i = 0; i < n; i++)
		cin >> v[i];
	for (int i = 0; i < 4; i++)
		cin >> o[i];
	bt(0, v, o, k);
	cout << ma << '\n' << mi;
}

void bt(int n, vector<int> v, vector<int> o, vector<int> k) {
	if (n == v.size() - 1) {
		int temp = v[0];
		for (int i = 0; i < k.size(); i++) {
			if (k[i] == 0) {
				temp += v[i + 1];
			}
			else if (k[i] == 1) {
				temp -= v[i + 1];
			}
			else if (k[i] == 2) {
				temp *= v[i + 1];
			}
			else {
				temp /= v[i + 1];
			}
		}
		if (temp < mi)
			mi= temp;
		if (temp > ma)
			ma = temp;
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (o[i] != 0) {
			o[i]--;
			k.push_back(i);
			bt(n + 1, v, o, k);
			k.pop_back();
			o[i]++;
		}
	}
	return;
}