백준 1010 / 다리 놓기

M개 중에 중복없이 N개를 고르는 경우의 수 : 

MC(콤비네이션)N

해결법은 생각해내기 쉽지만 문제는 수의 범위다.

0<N<=M<=30이기 떄문에

M=30 , N=15일 때 답인 30C15는 long long도 못담는다.

그렇기에 따로 함수를 만들어줘야되는데

큰 수의 표현인 Big integer는 구현이 힘들기 떄문에

그냥 간단한 함수를 만들었다.

30*29*28........*16*15

----------------------

15* 14*13.......*2*1

일때 분모에 있는 15부터 분자로 나누어 0되는 수를 찾은 후 나눈다음 15를 1로 만들어주는 함수.

코드는

#include <stdio.h>
#include <iostream>
#include<vector>
 
using namespace std;
long long ans = 1;
 
vector<int>a;
vector<int>b;
 
 
void check() {
    for (int i = 0; i < b.size(); i++) {
        for (int j = 0; j < a.size(); j++) {
            if (a[j] % b[i] == 0 && b[i]!=1) {
                a[j] = a[j] / b[i];
                b[i] = 1;
                break;
            }
        }
    }
 
    long long up=1;
    long long down=1;
 
 
    for (int i = 0; i < a.size(); i++) {
        up = up * a[i];
    }
    for (int i = 0; i < b.size(); i++) {
        down = down * b[i];
    }
    
    ans = up / down;
 
}
 
 
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
    int testcase;
    cin >> testcase;
 
    while (testcase--) {
        int n, m;
        cin >> n >> m;
        
        int c;
        c = n;
            
        if (n == 0 || m == 0) {
            ans = 0;
        }
        else {
            for (int i = 0; i < n; i++) {
                a.push_back(m);
                m--;
            }
            for (int i = 0; i < n; i++) {
                b.push_back(c);
                c--;
            }
 
            check();
    
        }
        cout << ans << endl;
        a.clear();
        b.clear();
        ans = 1;
 
    }
}

테스트케이스가 여러번이기 때문에 테스트가 끝난 후 초기화시켜주는 걸 잊지말자.