[c++] 수식만들기(DFS)

수식만들기

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int a[20], op[5], n, maxi=-2147000000, mini=2147000000;
void DFS(int L, int res){
	if(L==n){
		if(res>maxi) maxi=res;
		if(res<mini) mini=res;
	}
	else{
		if(op[0]>0){
			op[0]--;
			DFS(L+1, res+a[L]);
			op[0]++;
		}
		if(op[1]>0){
			op[1]--;
			DFS(L+1, res-a[L]);
			op[1]++;
		}
		if(op[2]>0){
			op[2]--;
			DFS(L+1, res*a[L]);
			op[2]++;
		}
		if(op[3]>0){
			op[3]--;
			DFS(L+1, res/a[L]);
			op[3]++;
		}
	}
}
	

int main(){
	freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	for(i=0; i<4; i++){
		scanf("%d", &op[i]);
	}
	DFS(1, a[0]);
	printf("%d\n%d\n", maxi, mini);
	return 0;
}

DFS 문제를 풀 때 항상 체크배열만 생각하다보니 처음에는 해당 인덱스가 체크배열에서 0인지만 체크하려고 했었다.

코드를 참고하니 체크배열에 들어오는 값이 연산자의 개수 이므로 

그 연산자를 사용했다는 의미로 op배열의 값에서 하나씩 빼주면 되었다.

빼주고나서 DFS함수를 실행한 후 다시 돌아오게되었을 때 빼주었던 값을 다시 더해주면 된다.

 

이 문제는 DFS를 사용하면서 합을 구하는 문제이므로 DFS함수에 파라미터를 전달해줄 때 

그 시점까지 더했던 값을 같이 전달해주어서 그 값부터 다시 더할 수 있도록 처리한다.