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

문제 바로가기

14888번: 연산자 끼워넣기

 

딱 문제를 읽어보면 백트래킹 냄새가 솔솔 ~

 

역시나 백트래킹으로 구현하니 아주 쉽게 풀 수 있었다

백트래킹으로 문제를 풀 때는, 기존의 상태에서 어떠한 연산이나 수행으로 바뀐 상태를 다시 원래대로 돌려놓는 것이 중요하다.

dfs()함수에서 다른 상태로 갈 때 바뀌는 값이 res와 2차원 배열 visited 이므로, 재귀함수를 호출한뒤 다시 원래의 res와 visited로 돌려주어야한다.

 

또한, digit(연산자 개수) == n-1은 재귀함수의 탈출조건이므로, 이때 최대값과 최소값을 갱신시켜준다.

 

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

using namespace std;

int n;
int _number[11];
int visited[10];

vector<int> _operator; //0:+, 1:-, 2:*, 3: /
long maxx = -1000000000, minn = 1000000000;

int calculate(long n1, long n2, int oper)
{
	long result = 0;
	switch (oper) {
	case 0:
		result = n1 + n2;
		break;
	case 1:
		result = n1 - n2;
		break;
	case 2:
		result = n1*n2;
		break;
	case 3:
		result = n1/n2;
		break;
	}

	return result;
}

void dfs(long res, int digit)
{
	if (digit == n - 1)
	{
		maxx = max(maxx, res);
		minn = min(minn, res);
		return;
	}
		

	for (int i = 0; i < _operator.size(); i++)
	{
		if (!visited[i]) {
			int tmp = res;
			res = calculate(res, _number[digit + 1], _operator[i]);
			visited[i] = 1;
			dfs(res, digit + 1);
			visited[i] = 0;
			res = tmp;
		}	
	}
	

}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> _number[i];
	}

	for(int i = 0; i<4; i++)
	{
		int tmp;
		cin >> tmp;
		for (int j = 0; j < tmp; j++)
		{
			_operator.push_back(i);
		}
	}

	dfs(_number[0], 0);

	cout << maxx << endl << minn << endl;
	return 0;

}