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

나의정답1. 공식1사용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int fac(int n) {
	if (n == 1) return 1;
	return n * fac(n - 1);
}

int nCr(int n, int r) {
	return fac(n) / (fac(r) * fac(n - r));
}

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, r;
	scanf("%d %d", &n, &r);
	printf("%d\n", nCr(n, r));
}

 

나의정답2. 공식2사용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int nCr(int n, int r) {
	if (r == 0 || n == r) return 1;

	return nCr(n - 1, r - 1) + nCr(n - 1, r);
}

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, r;
	scanf("%d %d", &n, &r);
	printf("%d\n", nCr(n, r));
}

 

나의정답3. 메모이제이션 이용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
int dy[21][21] = { 0 };
int nCr(int n, int r) {
	if (dy[n][r] > 0) return dy[n][r];
	if (r == 0 || n == r) return 1;
	return dy[n][r] = nCr(n - 1, r - 1) + nCr(n - 1, r);
}

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	int n, r;
	scanf("%d %d", &n, &r);
	printf("%d\n", nCr(n, r));
}