[코드트리] 연산자 배치하기

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/arrange-operator/description?page=1&pageSize=20

💻 문제 풀이 : C++

// 1. 숫자의 순서 배열 -> 정수 순서 X
// 2. 연산자의 순서 배열
// 3. 계산하기!!
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> num;
int minAns = 2134567890;
int maxAns = -2134567890;

// vector<int> num; -> 정수 순서 X
vector<int> oper;
vector<int> operSelected;
int used[15];

int calc(int one, int two, int oper)
{
	if (oper == 0)
		return one + two;
	if (oper == 1)
		return one - two;
	if (oper == 2)
		return one * two;
}

void dfs(int depth)
{
	if (depth >= n-1)
	{
		int tmpAns = num[0];
		for (int i = 0; i < n-1; i++)
		{
			tmpAns = calc(tmpAns, num[i+1], operSelected[i]);
		}
		minAns = min(tmpAns, minAns);
		maxAns = max(tmpAns, maxAns);
		return;
	}
	// n-1 개 중에서 n-1개 순서 고르기 (X)
	// (n-1)!
	for (int i = 0; i < n-1; i++)
	{
		if (used[i] == 1) continue;
		used[i] = 1;
		operSelected.push_back(oper[i]);
		dfs(depth + 1);
		used[i] = 0;
		operSelected.pop_back();
	}
}

void INPUT()
{
	cin >> n;

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

	int plus, minus, multi;
	cin >> plus >> minus >> multi;

	for (int i = 0; i < plus; i++)
		oper.push_back(0);
	for (int i = 0; i < minus; i++)
		oper.push_back(1);
	for (int i = 0; i < multi; i++)
		oper.push_back(2);
}

int main()
{
	INPUT();

	dfs(0);

	cout << minAns << " " << maxAns << endl;

	return 0;
}

📌 memo 😊