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

문제

14888번: 연산자 끼워넣기

풀이

백트래킹, 브루트포스 알고리즘

 

연산자의 수는 N - 1로 어떤 연산에서 사용되지 않는 연산자를 생각할 필요가 없고, 전체 연산자를 어떤 순서로 사용할지 정하면 된다. 

 

재귀 함수에서 현재까지 연산한 값(current)과 사용할 피연산자(operands[depth + 1]와 각 연산자의 남아 있는 수를 인자로 받는다. current와 피연산자를 남아 있는 연산으로 계산하고, 사용한 연산자를 1 줄여서 다음 재귀 함수로 넘어간다. 

이렇게 depth가 N - 1이 되면, 모든 연산자를 사용한 것이므로 최댓값과 최솟값과 current 값을 비교한다. 

코드

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int N;
int operands[11];
int operators[4];

int mini = INT_MAX;
int maxi = INT_MIN;

void solution(int current, int depth, int o0, int o1, int o2, int o3)
{
	if (depth == N - 1)
	{
		mini = min(mini, current);
		maxi = max(maxi, current);

		return;
	}

	// 각 연산자가 남아 있다면 current와 현재 피연산자로 연산한다.
	// 사용한 연산자는 -1하고, depth를 1늘려서 다음 피연산자로 넘어간다.
	if (o0 > 0)
	{
		solution(current + operands[depth + 1], depth + 1, o0 - 1, o1, o2, o3);
	}
	if (o1 > 0)
	{
		solution(current - operands[depth + 1], depth + 1, o0, o1 - 1, o2, o3);
	}
	if (o2 > 0)
	{
		solution(current * operands[depth + 1], depth + 1, o0, o1, o2 - 1, o3);
	}
	if (o3 > 0)
	{
		solution(current / operands[depth + 1], depth + 1, o0, o1, o2, o3 - 1);
	}
}

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

	cin >> N;

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

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

	solution(operands[0], 0, operators[0], operators[1], operators[2], operators[3]);

	cout << maxi << '\n' << mini;

	return 0;
}