[알고리즘] (DFS, 순열) 연산자 끼워넣기 (from. 이코테)

문제

N개의 수로 이루어진 수열 A,,42, ..., 1이 주어집니다. 또, 수와 수 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어집니다. 연산자는 덧셈 (+), 뺄셈(-), 곱셈(x), 나눗셈(: )으로만 이루어 져 있습니다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서. 수식을 하나 만들 수 있는데 이때 주어진 수의 순서 를 바꾸면 안됩니다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈 (+) 2개, 뺄셈 (-) 1개, 곱셈(x) 1개, 나눗셈(:) 1개인 경우에는 총 60가지의 식을 만들 수 있습니다. 예를 들 어. 다음과 같은 식을 만들 수 있습니다.
식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행해야 합니다. 또. 나눗셈은 정수 나눗셈 으로 몫만 취합니다. 음수를 양수로 나눌 때는 C++14의 기준을 따릅니다. 즉. 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같습니다. 이에따라서 위의 식 4개의 결과를 계산해보면 다음과 같습니다.

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구 하는 프로그램을 작성하세요.
입력 조건 • 첫째 줄에 수의 개수 N(2 S N S 11)이

 주어집니다.

---

입력

 

• 둘째 줄에는 A. A,..., AN이 주어집니다. (1 s A, ≤ 100)
• 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수. 곱셈
(x)의 개수, 나눗셈(: )의 개수입니다.

---

출력 

 

• 첫째 줄에 만들 수 있는 식의 결과의 최댓값을 출력합니다.
• 둘째 줄에는 최솟값을 출력합니다.
• 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어 집니다. 또한 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 - 10억보다 크거나 같고, 10 억보다 작거나 같습니다.

---

IDEAS

'+-*/' 연산자의 순열을 구한뒤 입력받은 수열과 대치시켜 연산을 진행하면 된다.

여기서 순열을 구하는것이 이번 문제의 관건인것 같은데, 이 과정에서 dfs 알고리즘을 사용했다.

연산이 완료된 값들을 벡터에 넣고 정렬하여 최솟값과 최댓값을 구해주면 된다.

---

배운점

• 벡터의 정렬

//정의
#include <algorithm>
template< class RandomIt >

void sort( RandomIt first, RandomIt last );

//사용 예시
std::vector<int> q;
sort(q.begin(), q.end()); //오름차차순 정렬

 

• 순열 즉, 수열의 모든 경우의 수를 얻어야 하는 문제는 dfs 알고리즘을 사용하자.

---

코드

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

std::vector<int>	vect_result;
int	*arr_num;
int	N;

int	operation(int n1, int n2, char op)
{
	int	result = 0;

	if (op == '+')
		result = n1 + n2;
	if (op == '-')
		result = n1 - n2;
	if (op == '*')
		result = n1 * n2;
	if (op == '/')
		result = n1 / n2;
	return (result);
}

void	generate_permutations(std::vector<char>& nums, std::vector<int>& permutation, std::vector<bool>& used)
{
	if (permutation.size() == nums.size())
	{
		int temp = arr_num[0];
		for (int i=0; i<N-1; i++)
		{
			temp = operation(temp, arr_num[i+1], permutation[i]);
		}
		vect_result.push_back(temp);
		return ;
	}
	for (int i=0; i<nums.size(); i++)
	{
		if (used[i] == false)
		{
			used[i] = true;
			permutation.push_back(nums[i]);
			generate_permutations(nums, permutation, used);
			permutation.pop_back();
			used[i] = false;
		}
	}
}

int	main(void)
{
	std::cin >> N;
	// int	arr_num[N];
	int	arr_op[4];
	std::vector<char>	nums;
	std::vector<int>	permutation;

	arr_num = new int[N];

	std::cin.ignore();
	for (int i=0; i<N; i++)
		std::cin >> arr_num[i];
	std::cin.ignore();
	for (int i=0; i<4; i++)
		std::cin >> arr_op[i];
	std::cin.ignore();

	for (int j=0; j<arr_op[0]; j++)
		nums.push_back('+');
	for (int j=0; j<arr_op[1]; j++)
		nums.push_back('-');
	for (int j=0; j<arr_op[2]; j++)
		nums.push_back('*');
	for (int j=0; j<arr_op[3]; j++)
		nums.push_back('/');

	std::vector<bool>	used(nums.size(), false);

	generate_permutations(nums, permutation, used);
	sort(vect_result.begin(), vect_result.end());
	std::cout << vect_result[vect_result.size()-1] << std::endl;
	std::cout << vect_result[0] << std::endl;

}