longlong의 크기를 넘어가버리기때문에 string을 이용하여 숫자로 변환후 다시 string을 이용하여 작업할 필요가있다.
앞으로도 longlong 그이상의 연산이 필요할때는 쓸수있도록 알아두자.
그외의 파스칼의 삼각형을 이용하였다
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
string factorial[101][101];
string bigNumAdd(string n1, string n2) { //숫자를 string으로 저장후 (result) 다시 숫자로 변환
int sum = 0;
string result;
while (!n1.empty() || !n2.empty() || sum) { //1의 자리부터 숫자후 변환
if (!n1.empty()) {
sum += n1.back() - '0';
n1.pop_back();
}
if (!n2.empty()) {
sum += n2.back() - '0';
n2.pop_back();
}
result.push_back((sum % 10) + '0'); //다시 string
sum /= 10;
}
reverse(result.begin(), result.end()); //1의자리부터 push 하였기 때문에 뒤집는다.
return result;
}
string comb(int n, int m) {
if (n == m || m == 0) {
return "1";
}
string& result = factorial[n][m];
if (result != "") {
return result; // 적혀있으면 그냥 리턴
}
result = bigNumAdd(comb(n - 1, m - 1), comb(n - 1, m)); // 파스칼의 삼각형 적용
return result; //memorization
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
cout << comb(n, m);
return 0;
}