(C++) - 백준(BOJ) 2407번 : 조합

www.acmicpc.net/problem/2407

2407번: 조합

조합, 큰 수 더하기 구현 문제였습니다.

 

풀이방법

 1. long long 범위를 초과하기 때문에 string으로 수를 중간에 바꿔줘야 overflow가 발생하지 않습니다.

 2. dfs를 통해 nCm = n-1Cm-1 + n-1Cm이라는 조합식을 구현할 수 있습니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, ans;
string comb[101][101];

string numToString(string a, string b){
    ll sum = 0;
    string ret;
    while(a.size() || b.size() || sum){
        if(a.size()){
            sum += a.back() - '0';
            a.pop_back();
        }
        if(b.size()){
            sum += b.back() - '0';
            b.pop_back();
        }
        ret.push_back((sum % 10) + '0');
        sum /= 10;
    }
    reverse(ret.begin(),ret.end());
    return ret;
}

string combination(int n, int m){
    if(n == m || m == 0) return "1";
    string &ret = comb[n][m];
    if(ret != "") return ret;
    ret = numToString(combination(n-1,m-1), combination(n-1,m));
    return ret;
}

int main(){
    cin >> n >> m;
    cout << combination(n,m);
}