BAEKJOON 1010 - 다리 놓기

문제: https://www.acmicpc.net/problem/1010

n 개 에서 k 개를 고르는 (순서 없는)조합의 가짓수를 구하는 이항계수를 구하는 문제입니다.

특히 다리가 겹치면 안된다는 조건이 있기에 순서에 무관하게 조합의 개수를 구해야 됩니다.

이항 계수를 구하는 방법은 이전에 포스팅 한 방법을 사용해 구했습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
const int MAX = 31;
 
int cache[MAX][MAX];
 
int getBinomialCoefficient(int n, int k)
{
    if (n == k || k == 0)
        return 1;
 
    if (cache[n][k] != -1)
        return cache[n][k];
 
    return cache[n][k] = getBinomialCoefficient(n - 1, k - 1) + getBinomialCoefficient(n - 1, k);
}
 
 
int main()
{
    int cases;
    cin >> cases;
    for (int i = 0; i < cases; i++)
    {
        int n, m;
        cin >> n >> m;
        memset(cache, -1, sizeof(cache));
        cout << getBinomialCoefficient(m, n) << endl;
    }
 
    return 0;
}