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

브루트포스 문제이다.

백트래킹을 사용하여 모든 경우를 탐색해주자. 

연산자 개수가 10개 밖에 안돼서 next_permutation으로 해결하는 방법도 있다.

1. 백트래킹

#include <bits/stdc++.h>
using namespace std;

int n;
int num[12];
int cal[4];
int maxANS = -1'000'000'001; // 답의 범위는 -10억 ~ 10억
int minANS = 1'000'000'001;

void recur(int sum, int cur) {
	// 한번의 탐색이 끝나면, 최댓값 최솟값 갱신
	if (cur == n) {
		maxANS = max(maxANS, sum);
		minANS = min(minANS, sum);
		return;
	}

	for (int i = 0; i < 4; ++i) {
		// i번 연산자가 남아있지 않은 경우 다음 연산자로 넘어감
		if (cal[i] == 0) continue;
        
		// i번 연산자를 1개 사용
		--cal[i];
		if (i == 0) recur(sum + num[cur], cur + 1);
		else if (i == 1) recur(sum - num[cur], cur + 1);
		else if (i == 2) recur(sum * num[cur], cur + 1);
		else if (i == 3) recur(sum / num[cur], cur + 1);
        
		// 사용이 끝났으니 사용한 연산자 반납
		++cal[i];
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> num[i];
	for (int i = 0; i < 4; ++i) cin >> cal[i];
	
	recur(num[0], 1);
	cout << maxANS << '\n' << minANS;
	return 0;
}

2. next_permutation()

#include <bits/stdc++.h>
using namespace std;

int num[11];
int maxANS = -1'000'000'001;
int minANS = 1'000'000'001;
vector<int> calc;

int main()
{
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, numOfCases;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> num[i];
        
	// 연산자 나열
	for (int i = 0; i < 4; i++)
	{
		cin >> numOfCases;
		while (numOfCases--) calc.push_back(i);
	}

	// 나올 수 있는 경우의 수 계산 == 팩토리얼 연산
	numOfCases = 1;
	for (int i = 1; i <= n - 1; i++) numOfCases *= i; 
	
	while(numOfCases--) {
		int tmp = num[0];
		for (int j = 1; j < n; j++)
		{
			switch (calc[j - 1])
			{
			case 0:
				tmp += num[j];
				break;
			case 1:
				tmp -= num[j];
				break;
			case 2:
				tmp *= num[j];
				break;
			case 3:
				tmp /= num[j];
				break;
			}
		}
		minANS = min(minANS, tmp);
		maxANS = max(maxANS, tmp);
		next_permutation(calc.begin(), calc.end()); // 다음 경우
	}

	cout << maxANS << '\n' << minANS;

	return 0;
}

가능하다고 했지 빠르다곤 안했다.. ㅎㅎ

백트래킹은 중간 연산 결과를 이용할 수 있어서 속도가 빠르지만,

이 풀이는 매 경우마다 계산을 다 해주어야해서 당연히 속도가 느리다.