1010 다리놓기

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

[1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net](https://www.acmicpc.net/problem/1010)

처음 문제를 봤을때 단순히 팩토리얼 계산을 한다음 나누는 방식을 이용하려고 했다.

그래서 식이 결국 nCr 의 결과를 나타내는 것을 확인 했고 이를

(n!) / ( n - r)! * r! 으로 단순히 계산하려고 하였으나 범위가 30까지였기 때문에 unsigned long long 으로도 벗어나는 것을 확인

할 수 있었다. 따라서

조합 분할이라는 것을 찾게 되었고 위를 하기위해서 nCr 이 (n - 1)C(r - 1) + (n - 1)C(r)임을 이용하여

해결 하고자 하였다. 매번 재귀를 돌면서 돌았던 부분들을 확인하는데 걸리는 시간이 너무 많았고 이를

nc 라는 배열을 만들어서 nc[n][r]의 번지에 가게 된 친구들은 미리 저장할 수 있도록 하였다. 위와 같이 코드를 짜게 되니

간단하게 통과할 수 있었따.

int nc[31][31];

unsigned long long combine(int x, int y)
{
    if (nc[x][y] != 0)
        return (nc[x][y]);
    if (y == x || x == 0)
    {
        return 1;
    }
    nc[x][y] = combine(x - 1, y - 1) + combine(x, y - 1);
    return (nc[x][y]);
}