[BOJ] 조합 2407번 C++

 

문제

nCm을 출력한다.

입력

 

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

 

접근 방식

 

조합 자체를 구하는 것은 쉽다

하지만 100C100일 경우

long long 의 범위를 넘어가기 때문에 큰 수 구하기 방식으로 풀어야 한다

 

찾아보다가 나는 배열 자체를 vector<int> 형식으로 풀이하는 방식으로 풀었다.

typedef로 vector<int>를 BigInt 형으로 선언한 후,

기존에 풀던 대로 dp 배열을 BigInt 형으로 선언해 사용해주면 된다.

 

코드 자체는 복잡했지만

알고보면 원래 조합을 구하는 dp 코드 그 자체임을 알 수 있다

 

코드

 

#include<bits/stdc++.h>
using namespace std;

typedef vector<int> BigInt;
BigInt dp[103][103];

BigInt add(BigInt a, BigInt b) {
    BigInt res;
    int carry = 0,sum = 0;
    int size = max(a.size(), b.size());

    for(int i=0; i<size || carry; i++) {
        if(i < a.size()) sum += a[i];
        if(i < b.size()) sum += b[i];
        sum += carry;
        res.push_back(sum%10);
        carry = sum / 10;
        sum = 0;
    }
    return res;
}


int main() {
    int n,m; cin>>n>>m;
    
    dp[0][0] = {1};
    for(int i=1; i<=100; i++) {
        dp[i][0] = {1};
        for(int j=1; j<=100; j++) {
            dp[i][j] = add(dp[i-1][j], dp[i-1][j-1]);
        }
    }

    BigInt res = dp[n][m];
    for(auto it = res.rbegin(); it != res.rend(); it++) cout<<*it;
}