알못에서 잘알까지

    10번 문제   

programmers.co.kr/learn/courses/30/lessons/43165

    내가 풀이한 답   

 더하는 경우와 빼는 경우만 고려하면 되므로 재귀 함수를 2번 호출하여 구하면 쉽게 구할 수 있다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int answer = 0;

void dfs(int level, int sum, vector<int> numbers, int target){
    if(level == numbers.size()){
        if(target==sum) {
            answer++;
        }
    }
    else {
        dfs(level+1, sum+numbers[level], numbers, target);
        dfs(level+1, sum-numbers[level], numbers, target);
    }
}

int solution(vector<int> numbers, int target) {
    
    dfs(0, 0, numbers, target);
    
    return answer;
}

    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;
}

    8번 문제   

    내가 풀이한 답   

 앞의 7번 문제를 응용하면 쉽게 풀 수 있다. 

 두 개의 부분집합으로 나뉘기 때문에 부분집합의 총 합과 (전체 총 합 - 부분집합의 총 합)이 같으면 두 부분 집합이 같게 된 점을 이용하면 쉽게 풀 수 있다.

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

void dfs(int level, int sum){
	if(level == n+1){
		if(total-sum == sum) flag = true; 
	}
	else {
		dfs(level+1, sum+a[level]);
		dfs(level+1, sum);
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i;
	cin >> n;
	for(i=1; i<=n; i++){
		cin >> a[i];
		total+=a[i];
	}
	
	dfs(1, 0);
	
	if(flag) cout << "YES";
	else cout << "NO";
	
	return 0;
}

    사이트의 답안   

#include<stdio.h>
int n, a[11], total=0;
bool flag=false;
void DFS(int L, int sum){
	if(sum>(total/2)) return;
	if(flag==true) return;
	if(L==n+1){
		if(sum==(total-sum)){
			flag=true;
		}		
	}
	else{
		DFS(L+1, sum+a[L]);
		DFS(L+1, sum);
	}
}
int main(){
	freopen("input.txt", "rt", stdin);
	int i;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
		total+=a[i];
	}
	DFS(1, 0);
	if(flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}