Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
2x2 격자의 왼쪽 위에서 출발하고, 오른쪽과 아래쪽으로만 이동할 수 있으면, 오른쪽 아래로 이동하는 데에는 정확히 6개의 경로만 있다.
20x20 격자에는 몇 개의 경로가 있는가?
--------------------------------------------------------------------------
격자를 만들고, 이동하는 형태로 반복문을 작성하면 해결 가능할 것 같았는데, 이상하게도 반복문이 만들어지지 않으면서 혼자 논리가 꼬이는 일이 계속되어 답을 구하는 데 많은 시간이 걸렸다. 그래도 아직 답을 구하는 규칙을 찾지 못한 26번에 비하면 빨리 답을 구한 편이긴 하다.
15번이면 비교적 앞쪽의 문제인데 해결방안을 못찾아 애먹으면서 답답했지만, 한 번 논리가 꼬여버린 논리를 푸는 것은 어려운 일이라는 것을 다시 한 번 느꼈고, 좋은 논리로 해결하지 못하고 단순하게 해결할 수 밖에 없어 답답했던 문제이다.
divide and conquer라는 분할정복 방법으로 접근할 수 밖에 없었고, 1x1에서는 2개, 2x2에서는 6개, 3x3에서는 20개로 늘어나는 과정을 쪼개어서(3x3 경로를 1x1, 2x2의 경로를 이용해 구하기) 이전 과정의 합계를 활용하는 규칙을 찾아 그것을 프로그램으로 해결하였다.
이제 생각해보니 전체 2n개의 경로에 n개의 한 방향을 입력하면 되는 것이어서 조합을 이용하면 간단히 답을 구할 수 있는 것이었다.