9. 특정 수 만들기(DFS 완전탐색: MS 인터뷰)

 

    9번 문제   

 

 

 

---

 

    내가 풀이한 답   

 

 7, 8번 문제와 비슷한 유형을 계속 풀다보니 재귀함수를 몇 번 써야 하는지가 중요하게 느껴졌다.  7번과 8번은 포함o, 포함 x로 2가지의 경우만 고려하면 됐지만 위 문제 같은 경우는 +, -, 포함x 총 3가지의 경우를 고려해야 한다. 

 

 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, m, a[11], count = 0;

void dfs(int level, int sum){
	if(level == n+1){
		if(m == sum) count++;
	}
	else {
		dfs(level+1, sum+a[level]);
		dfs(level+1, sum-a[level]);
		dfs(level+1, sum);
	}
}
	
int main() {
	//freopen("input.txt", "rt", stdin);
	int i;
	cin >> n >> m;
	for(i=1; i<=n; i++){
		cin >> a[i];
	}
	
	dfs(1, 0);
	
	if(count!=0) cout << count;
	else cout << -1; 
			
	return 0;
}

 

 

---

    사이트의 답안   

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int a[11], n, m, cnt=0;
void DFS(int L, int sum){
	if(L==n+1){
		if(sum==m){
			cnt++;
		}
	}
	else{
		DFS(L+1, sum+a[L]);
		DFS(L+1, sum);
		DFS(L+1, sum-a[L]);
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	DFS(1, 0);
	if(cnt==0) printf("-1\n");
	else printf("%d\n", cnt);
	return 0;
}