dfs 복습

선배님께서 코테를 공부할때 항상 이전에 푼 문제들을 다시 한번 풀고 새로운 문제를 받아들여라고 하셨다..

따라서 나는 앞으로 매일 이전에 푼 dfs문제들을 새롭게 다시 푼 후 새로운 문제들을 해결해나갈것이다.

 

56번

#include<iostream>
using namespace std;

int div(int v)
{
	if(v>3)
	{
		return 0;
	}
	else
	{
		cout << v << " ";
		div(v+1);
		
	}
}

int main()
{
	div(1);
}

 

57번

#include<iostream>
using namespace std;

int div(int v)
{
	int tmp = v;
	if(v<1)
	{
		return 0;
	}
	else
	{
		div(v/2);
		cout << tmp%2;
		
	}
}

int main()
{
	div(11);
}

 

58번

#include<iostream>
using namespace std;

int div1(int v)
{
	if(v>7)
	{
		return 0;
	}
	else
	{
		cout << v;
		div1(v*2);
		div1(v*2+1);
	}
}
int div2(int v)
{
	if(v>7)
	{
		return 0;
	}
	else
	{
		div2(v*2);
		cout << v;
		div2(v*2+1);
	}
}
int div3(int v)
{
	if(v>7)
	{
		return 0;
	}
	else
	{
		
		div3(v*2);
		div3(v*2+1);
		cout << v;
	}
}

int main()
{
	div1(1);
	cout << endl;
	div2(1);
	cout << endl;
	div3(1);
}

 

59번

#include<iostream>
using namespace std;
int ch[4];
int div(int v)
{
	if(v==4)
	{
		for(int i=1;i<4;i++)
		{
			if(ch[i]==1)
			{
				cout << i;
			}
		}
		cout << endl;
	}
	else
	{
		ch[v]=1;
		div(v+1);
		ch[v]=0;
		div(v+1);
	}
}

int main()
{
	div(1);
}

 

60번

#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(){
	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;
}

 

61번

#include<iostream>
using namespace std;
int n, a[11], total=0,cnt = 0;
bool flag=false;

int div(int v,int sum)
{
	if(v==n+1)
	{
		if(total==sum)
		{
			cnt++;	
		}
		
	}
	
	else
	{
		div(v+1,sum+a[v]);
		div(v+1,sum-a[v]);
		div(v+1,sum);
		
	}
	
}

int main()
{
	int tmp;
	cin >> n >> total;
	for(int i=1;i<=n;i++)
	{
		cin >> tmp;
		a[i] = tmp; 
	}
	div(1,0);
	cout << cnt;
}