[백준 14888번 C++풀이] - 연산자 끼워넣기

걸린시간: 21분

 

내가 백트래킹에 익숙해져서 그런건지, 아니면 그냥 문제가 쉬워서 그런건진 몰라도 구상과 구현시간은 별로 걸리지 않았다.

구상에 대해 약간 적자면,

먼저 배열의 크기만큼 배열을 만든후 그 배열 사이사이에 들어갈 연산자들의 개수를 받아준다.

그리고 그 사이에 들어갈 수 있는 연산자들을 고른후 4개중 하나를 고르는 경우를 반복적으로 진행하여, 모두 채웠으면 연산자를 계산하는 방식으로 처리했다.

 

#include <iostream>
#include <vector>

using namespace std;
vector <int> cul;
vector <int> c;
vector <int> s;
int big= -1000000001;
int small = 1000000001;
void t(int count);
int main()
{
	int a, b,d, n, m;
	cin >> a;
	for (int i = 0; i < a; i++)
	{
		cin >> b;
		c.push_back(b);
	}
	for (int i = 0; i < 4; i++)
	{
		cin >> b;
		cul.push_back(b);

	}
	s.resize(a-1, 0);

	
	t(0);
	cout << big << "\n" << small;


}


void t(int count)
{

	if (count == s.size())
	{
		int tem = c[0];
		for (int i = 1; i < c.size(); i++)
		{
			if (s[i - 1] == 0)
			{
				tem += c[i];
			}
			if (s[i - 1] == 1)
			{
				tem -= c[i];
			}
			if (s[i - 1] == 2)
			{
				tem *= c[i];
			}
			if (s[i - 1] == 3)
			{
				tem /= c[i];
			}
		}

		if (big < tem)
		{
			big = tem;
		}
		if (small > tem)
		{
			small = tem;
		}
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			if (cul[i] != 0)
			{
				cul[i]--;
				s[count] = i;
				t(count+1);
				cul[i]++;
				s[count] = 0;
			}
		}
	}
}