[백준][C++] 14888: 연산자 끼워넣기

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

 

백트래킹+브루트포스 문제입니다. 별로 고려할 건 없고.. 그냥 모든 경우의 수에 직접 계산해봐야 합니다. 연산자 우선순위같은건 없고 앞에서부터 뒤로 선입선출로 계산하면 됩니다

#include <bits/stdc++.h>
using namespace std;

int n;
int min_res, max_res;
vector<int> nums;

void calc(vector<char>& ops, int remain_plus, int remain_minus, int remain_mul, int remain_div) {
	if (remain_plus == 0 && remain_minus == 0 && remain_mul == 0 && remain_div == 0) {
		int ret = nums[0];
		for (int i = 0; i < n - 1; ++i) {
			switch (ops[i]) {
			case '+':
				ret += nums[i + 1];
				break;

			case '-':
				ret -= nums[i + 1];
				break;

			case '*':
				ret *= nums[i + 1];
				break;

			case '/':
				ret /= nums[i + 1];
				break;
			}
		}

		min_res = min(min_res, ret);
		max_res = max(max_res, ret);

		return;
	}


	if (remain_plus) {
		ops.push_back('+');
		calc(ops, remain_plus-1, remain_minus, remain_mul, remain_div);
		ops.pop_back();
	}
	if (remain_minus) {
		ops.push_back('-');
		calc(ops, remain_plus, remain_minus-1, remain_mul, remain_div);
		ops.pop_back();
	}
	if (remain_mul) {
		ops.push_back('*');
		calc(ops, remain_plus, remain_minus, remain_mul-1, remain_div);
		ops.pop_back();
	}
	if (remain_div) {
		ops.push_back('/');
		calc(ops, remain_plus, remain_minus, remain_mul, remain_div-1);
		ops.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	min_res = INT_MAX;
	max_res = INT_MIN;

	cin >> n;
	nums = vector<int>(n);
	for (auto& c : nums)
		cin >> c;

	int pl, mi, mu, di;
	cin >> pl >> mi >> mu >> di;
	vector<char> vc;
	calc(vc, pl, mi, mu, di);

	cout << max_res << '\n' << min_res << '\n';
	
	return 0;
}

컨디션이 안좋아서 그런지 코드가 넘 극혐이네요 ;;;; 여러분은 이렇게 짜지 마십쇼

넘피곤하니 리팩토링은 언젠가 하는걸로..