[BOJ] 1010번: 다리 놓기

1010번: 다리 놓기

풀이

문제 읽을 때부터 뭔가 조합의 느낌이 났는데 조합이었다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 nCr을 구현해주면 된다.

코드

#include <cstdio>
#include <cstring>
int n, r, D[31][31];

long long int nCr(int n, int r)
{
    if (n == r || r == 0)
        return D[n][r] = 1;
    if (r == 1)
        return D[n][r] = n;
    if (D[n][r])
        return D[n][r];
    return D[n][r] = (nCr(n - 1, r - 1) + nCr(n - 1, r));
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &n, &r);
        printf("%lld\n", nCr(r, n));
        memset(D, 0, sizeof(D));
    }
    return 0;
}