白駿2407組
質問リンク
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;
}
Reference
この問題について(白駿2407組), 我々は、より多くの情報をここで見つけました
https://velog.io/@trevor522/백준-2407-조합
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#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;
}
Reference
この問題について(白駿2407組), 我々は、より多くの情報をここで見つけました https://velog.io/@trevor522/백준-2407-조합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol