조합 2407번 [백준]

이번에 푼 문제는 조합 문제입니다. 입력으로 주어진 Combination에 대한 값을 출력하는 것인데,

long long으로 설정하고 계산해도 크기를 크게 초과하게 되었습니다.

 

따라서 저는 string을 이용하여 구현했습니다.

처음에는 string을 이용해서 구해보자니, 곱셈이여서 코드를 도무지 어떻게 짜야하는지 몰랐습니다.

하지만 파스칼의 삼각형을 이용하여, 덧샘을 이용해서(덧셈은 recursive으로 구현합니다.) 조합의 값을 구할 수 있었습니다.

 

#import<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n,k;
string factorial[101][101];//nCk을 저장하는 값
string stringAdd(string a,string b){//a + b 의 값을 factorial에 저장하고 그걸 return함
    int sum =0;
    string result;
    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();
        }
        result.push_back((sum % 10) +'0');
        sum /= 10;
    }
    reverse(result.begin(),result.end());
    return  result;
}
string combination(int a, int b){
    if(a == b || b == 0  )
        return "1";
    string & result =factorial[a][b];
    if(!result.empty())
        return result;//비어이지 않으면 저장된 값을 리턴
    // 저장되지 않은 값이라면, stringAdd함수를 이용하여, string값을 저장후 return하기.
    result = stringAdd(combination(a-1,b-1),combination(a-1,b));
    return result;
    //파스칼의 삼각형을 이용했음.
}
int main() {
    fast_io;
    cin>>n>>k;
    cout<<combination(n,k);
    return 0;
}

www.acmicpc.net/problem/2407