[C/C++] 백준 14888번 - 연산자 끼워넣기 (DFS, 백트래킹)

 

 

<DFS코드>

#include<iostream>
using namespace std;

int MAX = -1000000000; // -10억
int MIN = 1000000000; // 10억

int Operator[4]; // 연산자
int num[11]; // 입력 순열
int N;

void DFS(int plus, int minus, int multiple, int divide, int x, int sum)
{

	if (x == N - 1)
	{
		if (sum < MIN) MIN = sum;
		if (sum > MAX) MAX = sum;
	}

	if (plus > 0) DFS(plus - 1, minus, multiple, divide, x + 1, sum + num[x + 1]);
	if (minus > 0) DFS(plus, minus - 1, multiple, divide, x + 1, sum - num[x + 1]);
	if (multiple > 0) DFS(plus, minus, multiple - 1, divide, x + 1, sum * num[x + 1]);
	if (divide > 0) DFS(plus, minus, multiple, divide - 1, x + 1, sum / num[x + 1]);
}

int main()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> num[i];
	}

	for (int i = 0; i < 4; i++)
	{
		cin >> Operator[i];
	}

	DFS(Operator[0], Operator[1], Operator[2], Operator[3], 0, num[0]);

	cout << MAX << "\n" << MIN;
}

 

풀이는 간단하게 입력받은 순열을 고정시켜놓고 그 사이사이에 보유하고 있는 연산자들을 넣어서 모든 경우의 수를 따지고 그중에서 최댓값, 최솟값을 구하는 문제이다. 

예제 입력3을 살펴보면

"+" 2개
"-"1개
"*"1개
"/"1개

를 가지고있으며 가능한 조합은

1+2+3-4*5/6 = 1
1+2-3+4*5/6 = 3
1+2-3*4+5/6 = 0
...
...
...
1/2*3-4+5+6 = 7

이 중에서 최댓값, 최솟값은
1-2/3+4+5*6 = 54(최대)
1+2+3/4-5*6 = -24(최소) 
으로 DFS를 통해 모든 경우에서 최대, 최솟값을 구할 수 있다. 

 

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기