Problem 15 : Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner (without backtracking)?
시작점에서 끝점까지의 모든 경로는 가로 변과 세로 변으로 구성된다.
그리고, 모든 경로에서 경로의 길이는 같으며, 그 경로를 구성하는 가로 변 길이의 합과 세로 변 길이의 합은 서로 같다.
그럼, 각 점에서 오른쪽 방향(가로), 아래 방향(세로) 두 가지 방향을 선택하는 문제로 볼 수 있다. 결국, 이 문제는 정사각형이 주어졌을 때, 전체 경로 (= 가로의 경로 개수 + 세로의 경로 개수) 중에서 가로 개수와 세로 개수가 같은 경우가 몇 가지인지를 찾아내는 문제로 생각할 수 있다.
n by n 정사각형일 때 시작점에서 마지막점까지 가려면, 가로 n번, 세로 n번을 가야 한다.
따라서, 2n 개 중에서 가로 n개, 세로 n개를 선택하는 문제가 된다.
** 이 문제에 예시로 나오는 그림을 시계방향으로 45도 돌려서 보면,
파스칼의 삼각형(Pascal's triangle in wikipedia)의 한 부분이 떠오를 것이다.
예시) 2 by 2 grid
시작점에서 끝점까지의 모든 경로는 가로 변과 세로 변으로 구성된다.
그리고, 모든 경로에서 경로의 길이는 같으며, 그 경로를 구성하는 가로 변 길이의 합과 세로 변 길이의 합은 서로 같다.
그럼, 각 점에서 오른쪽 방향(가로), 아래 방향(세로) 두 가지 방향을 선택하는 문제로 볼 수 있다. 결국, 이 문제는 정사각형이 주어졌을 때, 전체 경로 (= 가로의 경로 개수 + 세로의 경로 개수) 중에서 가로 개수와 세로 개수가 같은 경우가 몇 가지인지를 찾아내는 문제로 생각할 수 있다.
n by n 정사각형일 때 시작점에서 마지막점까지 가려면, 가로 n번, 세로 n번을 가야 한다.
따라서, 2n 개 중에서 가로 n개, 세로 n개를 선택하는 문제가 된다.
** 이 문제에 예시로 나오는 그림을 시계방향으로 45도 돌려서 보면,
파스칼의 삼각형(Pascal's triangle in wikipedia)의 한 부분이 떠오를 것이다.
n <- 20
choose(2*n, n)
choose(2*n, n)
