[c++] 이항계수(메모이제이션), 친구인가(Union&Find 자료구조)

이항계수(메모이제이션)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int dy[21][21];
int DFS(int n, int r){
	if(dy[n][r]>0) return dy[n][r];
	
	if(n==r || r==0) return 1;
	else return dy[n][r]=DFS(n-1, r-1)+DFS(n-1, r);
}
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, m;
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS(n, m));	
	return 0;
}

 

친구인가(Union&Find 자료구조)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int unf[1001];
int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}
void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a]=b;
}
int main() {
	int i;
	//freopen("input.txt", "rt", stdin);
	int n, m, a ,b;

	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		unf[i]=i;
	}
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		Union(a, b);
	}
	scanf("%d %d", &a, &b);
	a=Find(a);
	b=Find(b);
	if(a==b) printf("YES");
	else printf("NO");

	return 0;
}