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

문제

 

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

---

Algorithm

문제에서 n의 개수는 2~11개, 연산자의 개수는 4개임을 알려줬으므로 각각 11개와 4개의 배열을 생성한다.

최대와 최소 역시 -10억 ~ 10억 사이기 때문에 각각 10억 1과 마이너스 10억 1로 설정한다.

answer함수에서는 재귀를 통해 더하기부터 차례로 계산한다. 

 

---

 

 

Code

#include <iostream>

using namespace std;

int n;
int operands[11];
int operators[4];
int ans_max = -1000000001;
int ans_min = 1000000001;

void answer(int result,int idx)
{
	if (idx == n)
	{
		if (result > ans_max)
			ans_max = result;
		if (result < ans_min)
			ans_min = result;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		if (operators[i] > 0)
		{
			operators[i]--;
			if (i == 0)
				answer(result + operands[idx], idx + 1);
			else if (i == 1)
				answer(result - operands[idx], idx + 1);
			else if (i == 2)
				answer(result * operands[idx], idx + 1);
			else
				answer(result / operands[idx], idx + 1);
			operators[i]++;
		}
	}
}

int main(void)
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> operands[i];
	for (int i = 0; i < 4; i++)
		cin >> operators[i];
	answer(operands[0],1);
	cout << ans_max << '\n' << ans_min;

	return 0;
}