[백준/BOJ] 백준 14888번 : 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

완전 탐색(브루트 포스)을 이용해 문제를 해결하였다.

덧셈은 0, 뺄셈은 1, 곱셈은 2, 나눗셈은 3으로 구별해 순열을 만들어 가능한 모든 연산자의 위치를 구해 연산 결과의 최댓값과 최솟값을 구하였다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int n;
	vector<int> a;
	int temp;
	vector<int> num; //각 연산자가 몇개 들어갔는지 표시
	vector<int> check; //순열을 만들기 위한 벡터
	int minresult = 1000000001;
	int maxresult = -1000000001;

	cin >> n;

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

	//연산자의 개수를 입력받는다.
	for (int i = 0; i < 4; i++)
	{
		cin >> temp;
		num.push_back(temp);
	}

	//각 연산자의 개수만큼
	//+는 0, -는 1, *는 2, /는 3을 넣는다.
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < num[i]; j++)
		{
			check.push_back(i);
		}
	}

	sort(check.begin(), check.end());

	//순열을 만들어서 연산자 위치가 될 수 있는 경우를 모두 구한다.
	do {

		int tempresult = a[0];

		for (int i = 1; i < n; i++)
		{
			if (check[i-1] == 0) //0이면 더하기
			{
				tempresult += a[i];
			}
			else if (check[i-1] == 1) //1이면 빼기
			{
				tempresult -= a[i];
			}
			else if (check[i-1] == 2) //2이면 곱하기
			{
				tempresult *= a[i];
			}
			else if (check[i-1] == 3) //3이면 나누기
			{
				tempresult /= a[i];
			}
		}
		//최댓값, 최솟값을 구한다.
		maxresult = max(maxresult, tempresult);
		minresult = min(minresult, tempresult);
		

	} while (next_permutation(check.begin(), check.end()));

	cout << maxresult << "\n";
	cout << minresult << "\n";

	return 0;
}