[Brute Force - 순열] 연산자 끼워넣기

 

예제 입력 1

2

5 6

0 0 1 0

예제 출력 1

30

30

예제 입력 2

3

3 4 5

1 0 1 0

예제 출력 2

35

17

예제 입력 3

6

1 2 3 4 5 6

21 1 1

예제 출력 3

54

-24

 

 

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

14888번: 연산자 끼워넣기

 

- 최대/최소값을 구할 때, 음수가 등장할 경우 주의해야한다.

최대값을 0으로 설정하고 문제를 풀면, 실제 결과의 최대값이 -1일 경우 올바른 결과를 구할 수 없게 되므로,

최소값으로 설정해야한다.

#include <stdio.h>
#include <malloc.h>

#define MINIMUM_VALUE (-2100000000)
#define MAX_SIZE (11)

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

#define PLUS (0)
#define MINUS (1)
#define MULTIPLIER (2)
#define DIVIDER (3)

int numbers[MAX_SIZE];
int N;

int operators[4]; // +,-,x,/

class OperatorsArray
{
	int items[MAX_SIZE];
	int itemsSize;
	int indexer[MAX_SIZE];

public:
	OperatorsArray()
	{
		itemsSize = 0;
	}

	void allocItems(int* operators, int size)
	{
		int idx = 0;

		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j < operators[i]; j++)
			{
				items[idx++] = i;
			}
		}

		itemsSize = size;
	}

	void initIndexer()
	{
		for (int i = 0; i < itemsSize; i++) indexer[i] = i;
	}

	bool next_permutation()
	{
		int i = itemsSize - 1;
		while ((i > 0) && (indexer[i - 1] > indexer[i])) i--;
		if (i <= 0) return false;

		int j = itemsSize - 1;
		while ((i < j) && (indexer[i - 1] > indexer[j]))j--;

		swap(indexer, i - 1, j);

		j = itemsSize - 1;
		while (i < j)
		{
			swap(indexer, i, j);
			i++; j--;
		}

		return true;
	}

	long long calcItem(int* data)
	{
		long long result = data[0];

		for (int i = 0; i < itemsSize; i++)
		{
			if (items[indexer[i]] == 0) result += data[i + 1];
			else if (items[indexer[i]] == 1) result -= data[i + 1];
			else if (items[indexer[i]] == 2) result *= data[i + 1];
			else result /= data[i + 1];
		}

		return result;
	}

private:
	void swap(int* arr, int a, int b)
	{
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
};
OperatorsArray o;

int main(void)
{
	long long maxResult = MINIMUM_VALUE;
	long long minResult = MINIMUM_VALUE;

	scanf("%d", &N);

	for (int i = 0; i < N; i++) 
		scanf("%d", &numbers[i]);

	for (int i = 0; i < 4; i++)
		scanf("%d", &operators[i]);

	o.allocItems(operators, N - 1);
	o.initIndexer();

	do
	{
		int calcResult = o.calcItem(numbers);

		maxResult = MAX(maxResult, calcResult);
		
		if (minResult == MINIMUM_VALUE) minResult = calcResult;
		else minResult = MIN(minResult, calcResult);

	} while (o.next_permutation());

	printf("%lld\n", maxResult);
	printf("%lld\n", minResult);

	return 0;
}

 

<STL 사용한 버전>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calc(vector<int>& a, vector<int>& b)
{
	int n = a.size();
	int ans = a[0];

	for (int i = 1; i < n; i++)
	{
		if (b[i - 1] == 0) ans = ans + a[i];
		else if (b[i - 1] == 1) ans = ans - a[i];
		else if (b[i - 1] == 2) ans = ans * a[i];
		else ans = ans / a[i];
	}

	return ans;
}

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

	int n;
	cin >> n;

	vector<int> a(n);

	for (int i = 0; i < n; i++)
		cin >> a[i];

	vector<int> b;
	for (int i = 0; i < 4; i++)
	{
		int cnt;
		cin >> cnt;

		for (int k = 0; k < cnt; k++)
		{
			b.push_back(i);
		}
	}

	sort(b.begin(), b.end());
	vector<int> result;

	do
	{
		int temp = calc(a, b);
		result.push_back(temp);
	} while (next_permutation(b.begin(), b.end()));

	auto ans = minmax_element(result.begin(), result.end());

	cout << *ans.second << '\n';
	cout << *ans.first << '\n';

	return 0;
}