[Algorithm] 백준 2407 조합 (C++)

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

2407번: 조합

알고리즘 분류

• 수학
• 조합론
• 임의 정밀도 / 큰 수 연산

 

문제 풀이

문제는 아주 단순하다. 조합 $ _nC_m $을 찾아내면 된다.
하지만 입력의 조건에서 나올 수 있는 최대값 $ _{100}C_{50} $ = 100891344545564193334812497256 로 $ 10^{29} $ 정도이다.
다행스럽게 __uint128_t 자료형으로 3 * 10^38까지의 숫자를 담을 수 있다.
하지만 위 자료형을 출력할 수 있는 포맷이 없어서 이 부분을 신경써주면 될 듯하다.

시간 초과를 방지하기 위해 문제를 dynamic programming 방식으로 풀 것이다.

 

코드 구현

#include <iostream>
#include <cmath>
using namespace std;

__uint128_t dp[101][101] = {0};

__uint128_t comb(int n, int m){
    if(m > n - m) m = n - m;

    if(m == 0) return 1;
    if(m == 1) return n;

    if(dp[n][m] != 0) return dp[n][m];

    return dp[n][m] = comb(n-1, m-1) + comb(n-1, m);
}

int main(){
    int N, M; cin >> N >> M;

    __uint128_t result = comb(N, M);

    string f = to_string((long long) (result / (__uint128_t) pow(10, 15))); 
    string s = to_string((long long) (result % (__uint128_t) pow(10, 15))); 
    
    if(f == "0") cout << s; 
    else cout << f + s; 
}