[백준 조합] 1010 C++

조합이란 ? N개의 숫자 중에서 순서에 상관없이 M개를 뽑는 것이라 이해했다.

예를들면 공동대표의 자리를 뽑는데, 대표의 자리는 공동 대표이므로 순서에 상관없는 경우이고 이를 조합으로 표현하면 

nCm으로 표현가능하다. 

 

백준에서는 메모제이션으로 이 문제를 풀었다.

#include <iostream>
#include <array>

using namespace std;

array<array<int, 30>, 30> memo;

int combination(int n, int r)
{
    if(memo[n][r]) 
        return memo[n][r];
    else
    {
        memo[n][r] = combination(n -1, r - 1) + combination(n - 1, r);
        return memo[n][r];
    }
}
int main()
{
    for(auto& x : memo) fill(x.begin(), x.end(), 0);
    
    for(int i = 0; i < 30; ++i)
        memo[i][0] = memo[i][i] = 1;
    
    int tcase, n, r;
    
    cin >> tcase;
    
    while(tcase--)
    {
        cin >> r >> n;
        
        cout << combination(n, r) << endl;
    }
    return 0;
}