[c++] 특정수 만들기(DFS), 병합정렬

특정수 만들기

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int n, m, ch[11], a[11], cnt=0, sum, total=0;
void DFS(int L, int sum){
	if(L==n+1) {
		if(sum==m) {
			cnt++;
			return;
		}
	}
	else {
		DFS(L+1, sum+a[L]);
		DFS(L+1, sum);
		DFS(L+1, sum-a[L]);
	}
}
int main() {
	int i;
	//freopen("input.txt", "rt", stdin);
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	DFS(1, 0);
	printf("%d", cnt);
		
	return 0;
}

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int n, m, i, ch[11], a[11], cnt=0, sum, path[11];
void DFS(int L, int sum){
	if(L==n+1) {
		if(sum==m) {
			cnt++;
			for(i=1; i<=n; i++){
				printf("%d ", path[i]);
			}
			puts("");
			
		}
	}
	else {
		path[L]=a[L];
		DFS(L+1, sum+a[L]);
		path[L]=0;
		DFS(L+1, sum);
		path[L]=-a[L];
		DFS(L+1, sum-a[L]);
		
	}
}
int main() {
	int i;
	freopen("input.txt", "rt", stdin);
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	DFS(1, 0);
	if(cnt==0) printf("%d\n", -1);
	else printf("%d", cnt);
		
	return 0;
}

 

병합정렬

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[101], tmp[101];
void devide(int lt, int rt){
	int i, mid, p1, p2, p3;
	if(lt<rt)
	{
		mid=(lt+rt)/2;
		devide(lt, mid);
		devide(mid+1, rt);
		p1=lt;
		p2=mid+1;
		p3=lt;
		while(p1<=mid && p2<=rt){
			if(a[p1] < a[p2]) tmp[p3++]=a[p1++];
			else tmp[p3++]=a[p2++];
			
		}
		while(p1<=mid){
				tmp[p3++]=a[p1++];
			}
		while(p2<=rt){
			tmp[p3++]=a[p2++];
		}
		for(i=lt; i<=rt; i++){
			a[i]=tmp[i];
		}
	}
}

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