BOJ 2407 조합

https://www.acmicpc.net/problem/2407

2407번: 조합

기존 조합 문제에서 한 레벨 위의 문제라 할 수 있는데.. 크게 두 가지 부분에서 그렇다.

 

1) 일단 nCm 에서 n과m의 범위가 100으로 매우 크다. 

2) long long을 쓰더라도 100C50의 결과값을 저장할 수 없다.

 

따라서 DP를 이용해 큰 수의 조합을 구하고, String을 이용해 결과값을 저장해 해결했다.

 

string Add(string a, string b) {
    string ans;
    long long sum = 0;
    while(!a.empty() || !b.empty() || sum) {
        if(!a.empty()) {
            sum += a.back() - '0';
            a.pop_back();
        }
        if(!b.empty()) {
            sum += b.back() - '0';
            b.pop_back();
        }
        ans.push_back((sum % 10) + '0');
        sum/=10; // carry 유지
    }
    reverse(ans.begin(), ret.end()); // 뒤에서부터 붙여넣었으므로 뒤집어줌
    return ans;
}

$C[n][m] = nCm$의 점화식은 모두 잘 알고있듯 다음과 같다.

 

$C[n][m] \begin{cases}C[n-1][m]\\C[n-1][m-1]\end{cases}$

 

Bottom-Up을 이용해 위 점화식을 구현하면 다음과 같다.

 

string dp[101][101];

string C_recur(int n, int m) { // 재귀
    if(n == m || m == 0)
        return "1";
    if(!C[n][m].empty())
        return C[n][m];
    return C[n][m] = add(C_recur(n-1, m), C_recur(n-1, m-1));
}

string C_for() { // 반복문
    for(int i=0;i<=N;++i)
        C[i][0] = "1";
    for(int j=1;j<=M;++j) {
        for(int i=1;i<=N;++i){
            C[i][j] = add(C[i-1][j], C[i-1][j-1]);
        }
    }
    return C[N][M];
}