백준 14888번 연산자 끼워넣기 C/C++ 풀이

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

 

이 역시 Brute force 문제.

 

재귀함수를 이용해서 문제를 풀었다.

 

어떻게든 재귀함수를 이용해서 완전탐색을 풀려고 끙끙 앓다보니 재귀함수 구현하는 능력이 레벨업 된 것 같다..ㅎㅎㅎ,,,,

 

아래는 재귀함수를 이용한 풀이

 

#include <stdio.h>

FILE* in = fopen("input.txt", "r");

#define MAX 11

int n;
int input_array[MAX];
int sign[4];
int checked[4];
int max = -1000000000;
int min = 1000000000;

// 부호 숫자에 따른 계산값 출력해주는 함수
int calc(int type, int ret, int idx) {
	int ans = ret;
	switch (type)
	{
		case 0:
			ans += input_array[idx];
			break;
		case 1:
			ans -= input_array[idx];
			break;
		case 2:
			ans *= input_array[idx];
			break;
		case 3:
			ans /= input_array[idx];
			break;
	}
	return ans;
}

//재귀함수로 구현한 dfs
void dfs(int selected, int ret) {
	if (selected == n - 1)
	{
		if (ret > max)
			max = ret;
		if (ret < min)
			min = ret;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		if (checked[i] < sign[i])
		{
			checked[i]++;
			dfs(selected + 1, calc(i, ret, selected + 1));
			checked[i]--;
		}
	}
}

int main() {
	fscanf(in, "%d", &n);
	for (int i = 0; i < n; i++)
		fscanf(in, "%d", &input_array[i]);
	for (int i = 0; i < 4; i++)
		fscanf(in, "%d", &sign[i]);
	dfs(0, input_array[0]);
	printf("%d\n%d", max, min);
	return 0;
}