백준 1010번. 다리 놓기 (C++)

 

#include <stdio.h>

int N, M;
long long c[31][31];

void combination()
{
    c[1][0] = 1;
    c[1][1] = 1;

    for (int i = 2; i <= 30; i++)
    {
        c[i][0] = 1;
        for (int j = 1; j <= 30; j++)
        {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
}

int main()
{
    combination();
    int tc;
    scanf("%d", &tc);
    for (int t = 1; t <= tc; t++)
    {
        scanf("%d %d", &N, &M);

        printf("%lld\n", c[M][N]);
    }
    return 0;
}

nCr을 미리 배열에 담아놓는다!!

nCr = (n-1)C(r-1) + (n-1)C(r)을 이용!!