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

모든 경우의 수를 다 고려해준다.

#include <stdio.h>
int n;
int min = 1000000001;
int max = -1000000001;
int arr[12];
void DFS(int plus, int minus, int mult, int div, int x, int sum)
{
	if (x == n - 1)
	{
		if (max < sum)
			max = sum;
		if (min > sum)
			min = sum;
	}
	if (plus > 0)
		DFS(plus - 1, minus, mult, div, x + 1, sum + arr[x + 1]);
	if (minus > 0)
		DFS(plus, minus - 1, mult, div, x + 1, sum - arr[x + 1]);
	if (mult > 0)
		DFS(plus, minus, mult - 1, div, x + 1, sum * arr[x + 1]);
	if (div > 0)
		DFS(plus, minus, mult, div - 1, x + 1, sum / arr[x + 1]);
}

int main()
{
	int plus, minus, mult, div, i;
	scanf("%d", &n);
	i = 0;
	while (i < n)
	{
		scanf("%d", &arr[i]);
		i++;
	}
	scanf("%d %d %d %d", &plus, &minus, &mult, &div);
	DFS(plus, minus, mult, div, 0, arr[0]);
	printf("%d\n%d", max, min);
}

다른 접근법으로는 https://wisdom-990629.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-14888%EB%B2%88-%EC%97%B0%EC%82%B0%EC%9E%90-%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0
순열로 생각해서 swap하는 방법또한 존재한다.