15. 20X20그리드의 좌상단에서 출발할 때 우하단으로 가는 길의 개수는?

Starting in the top left corner of a 2X2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20X20 grid?

2X2그리드의 좌상단에서 우하단으로 가는 길은 6개가 있다.

20X20그리드에선 몇개의 길이 있는가

파스칼의 삼각형을 이용해 풉니다.

1

1     1

1     2     1

1     3     3     1

1     4     6     4     1

1     5     10    10    5     1

1

1C0     1C1

2C0     2C1     2C2

3C0     3C1     3C2     3C3

4C0     4C1     4C2     4C3     4C3

5C0     5C1     5C2     5C3     5C4     5C5

nXn그리드에서 길의 개수는 2nCn 입니다.

#include <stdio.h> long long combi(long long n, long long r) { if(r==0) return 1; return (((n-r+1)*combi(n,r-1))/r); } int main() { printf("%lld", combi(40, 20)); return 0; }