[백준][C++] 15658: 연산자 끼워넣기 (2)

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

 

백트래킹, 브루트포스 문제입니다. 가능한 계산식을 다 만들어보고 계산하면 끝입니다.

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

int mx=INT_MIN, mn=INT_MAX;
const char op[] = { '+', '-', '*', '/' };

void backtrack(const vector<int>& nums, vector<char>& picked, vector<int>& remain, int toPick) {
	if (toPick == 0) {
		int res = nums.front();
		auto it = nums.begin() + 1;

		for (auto& p : picked) {
			switch (p) {
			case '+':
				res += *it;
				break;

			case '-':
				res -= *it;
				break;

			case '*':
				res *= *it;
				break;

			case '/':
				res /= *it;
				break;

			default:
				assert(1);
			}

			++it;
		}

		mx = max(mx, res);
		mn = min(mn, res);

		return;
	}

	for (int i = 0; i < 4; ++i) {
		if (remain[i]) {
			--remain[i];
			picked.push_back(op[i]);
			
			backtrack(nums, picked, remain, toPick-1);
			
			++remain[i];
			picked.pop_back();
		}
	}
}

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

	int n;
	cin >> n;

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

	vector<int> remain(4);
	for (auto& c : remain)
		cin >> c;

	vector<char> ops;
	backtrack(v, ops, remain, n - 1);

	cout << mx << '\n' << mn << '\n';

	return 0;
}

소스가 좀 긴데 다른 사람들 소스 보니 더 깔끔하게 푸는 법이 있네요

backtrack 함수가 결과값이랑 현재까지 계산한 수의 개수를 인자로 넘기면 됩니다. 나머지 인자들은 그냥 다 전역변수에 써놓습니다

이러면 훨씬 깔끔해질겁니다