백준 14888 연산자 끼워넣기 C언어 - DFS 완전탐색

N개의 수와 N-1개의 연산자를 조합하는 문제이다.

다행스럽게도 연산순서는 우선순위를 무시하고 앞에서부터 차례대로 계산하고

나누기 (/)는 음수를 양수로 나눌 경우 절대값을 나눈 몫을 음수로 바꿔서 넣는다.

즉 -5 / 2 는 -(5/2) 와 동일한 결과를 가져야한다.

 

연산은 DFS를 통해 미리 만들어 배열에 저장해놓고 사용하였다.

그러지 않고 DFS를 들어가면서 계산결과를 전달해줘도 되지만, 

그냥 이렇게 생각하기가 편해서 이렇게 구현하였다.

 

주의할 점은 중간이나 마지막 계산결과가 -10억~10억이기 때문에 평소 하던 것처럼 MAX 를 987654321로 두면

10억보다 작은 값이기 때문에 결과가 틀리게 나온다.

 

그것 외엔 주의할 점은 없다.

DFS 는 4가지 경우를 가진 Tree 형태로 구성하였고, op[4]에 저장된 +-*/의 개수가 남았을 경우

그것을 빼가면서 DFS로 들어가게 구현하였다.

#include <stdio.h>

int N,M;
int A[12];
int op[4];//+-*/
int cal[11];
int min = 1000000000+1;
int max=-1000000000-1;
//연산결과
int calculate() {
	int ret = A[0];
	for (int i = 1; i < N; i++) {
		int OP = cal[i - 1];
		switch (OP) {
		case 0:
			ret += A[i];
			break;
		case 1:
			ret -= A[i];
			break;
		case 2:
			ret *= A[i];
			break;
		case 3:
			if (ret < 0) {
				int tmp = -ret / A[i];
				ret = -tmp;
			}
			else {
				ret /= A[i];
			}
			break;
		}
	}
	if (ret < min) min = ret;
	if (ret > max) max = ret;
	return 0;
}


//dfs 로 연산기호 완전탐색
//cal 배열 만들고 A와 계산
int solve(int num) {
	if (num == M ) {
		calculate();
		return 0;
	}
	if (op[0]) {
		op[0]--;
		cal[num] = 0;
		solve(num + 1);
		op[0]++;
		cal[num] = 0;
	}
	if (op[1]) {
		op[1]--;
		cal[num] = 1;
		solve(num + 1);
		op[1]++;
		cal[num] = 0;
	}
	if (op[2]){
		op[2]--;
		cal[num] = 2;
		solve(num + 1);
		op[2]++;
		cal[num] = 0;
	}
	if (op[3]) {
		op[3]--;
		cal[num] = 3;
		solve(num + 1);
		op[3]++;
		cal[num] = 0;
	}
	return 0;

}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	scanf("%d %d %d %d", op, op + 1, op + 2, op + 3);
	for (int i = 0; i < 4; i++) {
		M += op[i];
	}
	solve(0);
	printf("%d\n%d", max,min);
}