[Brute Force - 재귀] 연산자 끼워넣기

 

예제 입력 1

2

5 6

0 0 1 0

예제 출력 1

30

30

예제 입력 2

3

3 4 5

1 0 1 0

예제 출력 2

35

17

예제 입력 3

6

1 2 3 4 5 6

2 1 1 1

예제 출력 3

54

-24

 

- 각 연산자의 개수를 int operators[4]로 선언하고 파라미터로 int* opreators를 넘겨주고 재귀로 짰더니 call by reference 때문에 결과 한번 나오면 모두 종료되어버림 -> 그냥 plus, minus, mutiply, divide 4개 변수를 각각 선언해버림

 

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

 

#include <stdio.h>

#define MAX_VALUE (2147483647)
#define MIN_VALUE (-2147483648)

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX_COUNT (11)

int N;
int numbers[MAX_COUNT] = { 0, };
int plus, minus, multiply, divide;

int maxResult = MIN_VALUE;
int minResult = MAX_VALUE;

void go(int* numbers, int start, int curValue, int plus, int minus, int multiply, int divide)
{
	if (start == N)
	{
		maxResult = MAX(maxResult, curValue);
		minResult = MIN(minResult, curValue);
		return;
	}

	if (plus > 0)
	{
		go(numbers, start + 1, curValue + numbers[start], plus-1, minus, multiply, divide);
	}
	if (minus > 0)
	{
		go(numbers, start + 1, curValue - numbers[start], plus, minus-1, multiply, divide);
	}
	if (multiply > 0)
	{
		go(numbers, start + 1, curValue * numbers[start], plus, minus, multiply-1, divide);
	}
	if (divide > 0)
	{
		go(numbers, start + 1, curValue / numbers[start], plus, minus, multiply, divide-1);
	}
}

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &numbers[i]);
	}

	scanf("%d", &plus);
	scanf("%d", &minus);
	scanf("%d", &multiply);
	scanf("%d", &divide);

	go(numbers, 1, numbers[0], plus, minus, multiply, divide);


	printf("%d\n%d\n", maxResult, minResult);

	return 0;
}