[BOJ] 14888 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

아이디어

1, dfs로 숫자를 돌면서 연산자가 들어 갈 수 있는 모든 경우의 수를 탐색하면서 만들 수 있는 최대값과 최소값을 구한다.

 

#include <cstdio>
#include <vector>
using namespace std;


int max_num = -1000000001;
int min_num = 1000000001;
int num;
vector<int> num_arr;
vector<int> operator_num;

void dfs(int num_idx, int res) {

	if (num_idx == num) {
		if (res > max_num) {
			max_num = res;
		}

		if (res < min_num) {
			min_num = res;
		}

		return;
	}
	
	//덧셈이 남아 있을 경우
	if (operator_num[0] != 0) {
		operator_num[0]--;
		dfs(num_idx + 1, res + num_arr[num_idx]);
		operator_num[0]++;
	}
	
	//밸셈이 남아 있을 경우
	if (operator_num[1] != 0) {
		operator_num[1]--;
		dfs(num_idx + 1, res - num_arr[num_idx]);
		operator_num[1]++;
	}

	//곱셈이 남아 있을 경우
	if (operator_num[2] != 0) {
		operator_num[2]--;
		dfs(num_idx + 1, res * num_arr[num_idx]);
		operator_num[2]++;
	}

	//나눗셈이 남아 있을 경우
	if (operator_num[3] != 0) {
		operator_num[3]--;
		dfs(num_idx + 1, res / num_arr[num_idx]);
		operator_num[3]++;
	}


}

int main()
{
	int temp;

	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		scanf("%d", &temp);
		num_arr.push_back(temp);
	}
	for (int i = 0; i < 4; i++) {
		scanf("%d", &temp);
		operator_num.push_back(temp);
	}


	dfs(1,num_arr[0]);

	printf("%d\n", max_num);
	printf("%d\n", min_num);


	return 0;
}