[백준 C++] 14888 : 연산자 끼워넣기

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

DFS로 구현하였다.

연산자 우선 순위를 무시하는 것, 나눗셈은 정수 나눗셈으로 몫만 취한다 등등 조건 덕분에 풀기 쉬운 문제이다.

---

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

using namespace std;

vector<int> list;

int maxValue = INT_MIN;
int minValue = INT_MAX;
int N;

void calculate(int add, int sub, int mul, int div, int depth, int value)
{
	if (depth == N)
	{
		maxValue = max(maxValue, value);
		minValue = min(minValue, value);
		return;
	}

	if (add != 0)
		calculate(add - 1, sub, mul, div, depth + 1, value + list[depth]);
	if (sub != 0)
		calculate(add, sub - 1, mul, div, depth + 1, value - list[depth]);
	if (mul != 0)
		calculate(add, sub, mul - 1, div, depth + 1, value * list[depth]);
	if (div != 0)
		calculate(add, sub, mul, div - 1, depth + 1, value / list[depth]);
	
	return;
}

int main()
{
	int operators[4];

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		list.push_back(temp);
	}

	for (int i = 0; i < 4; i++)
	{
		int temp;
		cin >> temp;

		operators[i] = temp;
	}

	calculate(operators[0], operators[1], operators[2], operators[3], 1, list[0]);

	cout << maxValue << "\n" << minValue << endl;
}

참고로 백준에서는 INT_MAX와 INT_MIN를 사용하고 싶다면 #include <limits>가 아닌 #include <climits>를 사용해야 한다.