Euler Problem 15

문제 내용

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

How many routes are there through a 2020 grid?

처음에 이 문제를 보았을 때 의사결정나무 구조를 만들어 풀어보고자 하였다. 그러나 경우의 수가 지나치게 늘어나고, VBA에서 트리 데이터 구조를 사용하려면 시간이 많이 들어가기 때문에 또 다른 방법이 없는가를 생각하였다. 초등학교 6-나 수학에 이와 유사한 문제가 있다. 아래 그림과 같이 2*2 그리드에서 시작점에서 종착점으로 가는 가장 빠른 길이 몇 가지가 되는 가를 묻는 문제들이 있다. 각 점을 (a, b)라고 할 때, a 또는 b가 0인 점[ (0,1),(0,2),(1,0), (2,0)]은 들어오는 길이 1개이다. (1,1)점은 (0,1)의 1개와 (1,0)의 1개를 합쳐 2개이다. (1,3)점은 (0,2)의 1개와 (1,1)의 2개를 합쳐 3개가 된다. 이런식으로의 변화를 20*20 그리드에 적용하기 위해 프로그래밍을 하였다.
 

 

Sub Euler15()
    Const N = 20
    Dim Grid(N + 1, N + 1)
    Dim a, b
    For a = 1 To N
        Grid(0, a) = 1
        Grid(a, 0) = 1
    Next
    For a = 1 To N
        For b = 1 To N
            Grid(a, b) = Grid(a - 1, b) + Grid(a, b - 1)
        Next
    Next
    Debug.Print Grid(N, N)
End Sub