[백준/BOJ] 백준 15658번 : 연산자 끼워넣기 (2)

www.acmicpc.net/problem/15658

15658번: 연산자 끼워넣기 (2)

vector<int> num;을 만들어 연산자의 개수를 저장하였다. 그래서 num[i] > 0 인 i연산자(0:덧셈 1:뺄셈 2:곱셈 3:나눗셈)만을 이용해서 연산자 수열을 만들고 그 수열을 이용한 결과값을 만든다. 만들어질 수 있는 모든 수열을 확인해서 결과값의 최댓값과 최솟값을 구한다.

 

코드

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

int n;
vector<int> a;
vector<int> num;
int max_r = -1000000001;
int min_r = 1000000001;

int Solve(vector<int>& selected)
{
	int ret = 0;

	//연산자를 n-1개 골랐을때
	if (selected.size() == n - 1)
	{
		//해당 연산자 수열을 이용한 결과 값을 구한다
		ret = a[0];
		for (int i = 0; i < selected.size(); i++)
		{
			//덧셈일때
			if (selected[i] == 0)
			{
				ret += a[i + 1];
			}

			//뺄셈일때
			else if (selected[i] == 1)
			{
				ret -= a[i + 1];
			}

			//곱셈일때
			else if (selected[i] == 2)
			{
				ret *= a[i + 1];
			}

			//나눗셈일때
			else if (selected[i] == 3)
			{
				ret /= a[i + 1];
			}
		}

		return ret;
	}

	//연산자(0:덧셈 1:뺄셈 2:곱셈 3:나눗셈)들을 확인하면서 연산자로 쓸 수 있는지 확인해 연산자 수열을 만든다
	for (int i = 0; i < 4; i++)
	{
		//i연산자를 쓸수 있을때(개수가 남아 있을때)
		if (num[i] > 0)
		{
			//selected에 추가, 해당 연산자 개수 감소
			selected.push_back(i);
			num[i]--;

			ret = Solve(selected);
			max_r = max(max_r, ret);
			min_r = min(min_r, ret);

			//selected에서 제거, 해당 연산자 개수 증가
			selected.pop_back();
			num[i]++;
		}
	}

	return ret;
}

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

	int input;
	vector<int> selected;

	cin >> n;

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

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

	Solve(selected);

	cout << max_r << "\n";
	cout << min_r;


	return 0;
}