[class4] (백준 2407) 조합

문제

_nC_m을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

_nC_m을 출력한다.

제한

예제 입력 1

100 6

예제 출력 1

1192052400

힌트

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론
• 임의 정밀도 / 큰 수 연산

#include <iostream> 
#include <algorithm>
using namespace std;
string arr[200][200];

string addNum(string str1, string str2)
{
	if (str1.length() > str2.length())
	{
		string temp = str2;
		str2 = str1;
		str1 = temp;
	}

	string temp = "";
	int len1 = str1.length();
	int len2 = str2.length();
	int templen = len2 - len1;

	int place = 0;
	for (int i = len1 - 1; i >= 0; i-- )
	{
		int sum = str1[i] - '0' + str2[i + templen] - '0' + place;
		temp.push_back(sum % 10 + '0');
		place = sum / 10;
	}

	for (int i = templen - 1; i >= 0; i--)
	{
		int sum = str2[i] - '0' + place;
		temp.push_back(sum % 10 + '0');
		place = sum / 10;
	}

	if (place > 0)
	{
		temp.push_back(place + '0');
	}

	reverse(temp.begin(), temp.end());
	return temp;
}

string GetResult(int n, int m)
{
	if (n == m || m == 0)
	{
		arr[n][m] = "1";
		return "1";
	}

	if (arr[n][m] != "")
	{
		return arr[n][m];
	}
	else
	{
		arr[n - 1][m - 1] = GetResult(n - 1, m - 1);
		arr[n - 1][m] = GetResult(n - 1, m);
		return addNum(arr[n - 1][m - 1], arr[n - 1][m]);
	}
}

int main() 
{ 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, M;
	cin >> N >> M;
	cout << GetResult(N, M);
	return 0;
}