백준 14888 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

본문제에 대한 풀이의 해법에 대한 힌트는 덧셈, 뻴셈, 곱셈, 나눗셈의 개수가 입력으로 주어진다는 것이다.

따라서 각 연산을 매핑할 숫자로 define 하고 개수가 정해져있기 때문에 N-1 개짜리 배열을 만들 수 있고 이숫자 배열의 가능한 모든 조합들을 순회해 가면서 최대 결과값을 업데이트 하도록 구현하면 된다.

 

예를들어 연산자 개수가 2 1 1 1 이라면 더하기 2개 , 뻬기 1개 , 곱하기 1개 , 나누기 한개 라는 뜻이다.

그럼 { + , + , - , * , / } 배열을 만들수 있고, 더하기가 0 이고 뻬기가 1이고 곱하기가 2이고 나누기가 3으로 매핑된다면 

{ 0, 0, 1, 2, 3 } 의 배열을 만들 수 있다. 이 배열의 모든 가능한 순열을 순회하면서 최대값을 구하면 된다.

 

구현된 코드는 아래와 같다.

 

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

using namespace std;

#define DEFAULT_MAX -1000000000
#define DEFAULT_MIN 1000000000

int calc(int &op1, int &op2, int m)
{
	if (m == 0) return op1 + op2;
	if (m == 1) return op1 - op2;
	if (m == 2) return op1 * op2;
	if (m == 3) return op1 / op2;

	return -1;
}

int main()
{
	int nrNum;
	cin >> nrNum;
	vector<int> nums(nrNum);
	for (int i = 0; i < nrNum; i++)
	{
		cin >> nums[i];
	}

	vector<int> opList;
	int n;
	for (int i = 0; i < 4; i++)
	{
		cin >> n;
		for (int j = 0; j < n; j++)
			opList.push_back(i);
	}

	int resultMax = DEFAULT_MAX;
	int resultMin = DEFAULT_MIN;
	do
	{
		int result = nums[0];
		for (int i = 1; i < nrNum; i++)
		{
			result = calc(result, nums[i], opList[i - 1]);
		}
		resultMax = max(resultMax, result);
		resultMin = min(resultMin, result);
	} while (next_permutation(opList.begin(), opList.end()));

	cout << resultMax << endl;
	cout << resultMin << endl;

	return 0;
}