[白俊/c+]2407番組

9746 ワード
backjoon テキストリンク
2407問題リンク

質問する


nCMを出力します.

入力


nとmを与える.(5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

しゅつりょく


nCMを出力します.

に答える


この問題で最も注意しなければならない部分は資料型の範囲です.c++の資料タイプは以下の通りです.
データ型範囲(署名済み)int-24748648～2147483647未署名int 0～4294967295(署名済み)long(int)-2474863647未署名long(int)0～4294967295
最大範囲であっても整数型は4294967295しか入力できず、nおよびmは100に入力できるため、4294967295を超えるしかない.したがって,値の資料型を文字列として扱う.
また,組合せデータの取得ロジックはパスカルの三角形と覚書により簡略化される.
詳細については、以下を参照してください.👇
[アルゴリズム]パスカルの三角形
［アルゴリズム］動的計画（Dynamic Programming，DP）

ソースコード

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int N, M;
string factorial[101][101];

string bigNumAdd(string n1, string n2) {
    int sum = 0;
    string result; //1의 자리부터 더하기
    
    while (n1.empty() == false || n2.empty() == false || sum) {
        if (n1.empty() == false) {
            sum += n1.back() - '0'; n1.pop_back();
        }
        
        if (n2.empty() == false) {
            sum += n2.back() - '0';
            n2.pop_back();
        }
        
        result.push_back((sum % 10) + '0');
        sum /= 10;
        
    } //역순이므로 다시 역순
    
    reverse(result.begin(), result.end());
    return result;
}

string combination(int n, int r) {
    if (n==r || r==0) return "1";
    
    string &result = factorial[n][r]; // 참조형 변수
    
    //memoization
    if (result != "") return result;
    
    //파스칼삼각형
    result = bigNumAdd(combination(n-1, r-1), combination(n-1, r)); return result;
    
}

int main() {
    cin >> N >> M;
    cout << combination(N, M);
}

正解


面接官はあなたのシリーズを「笑わせる」ことができます:配列はあなたを重くして何種類ができますか?
Rails5.2のcredentialsの使い方