프로젝트 오일러 문제 15

Lattice paths

Problem 15

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?

20×20크기의 격자에서 왼쪽 위 시작 점부터 오른쪽 아래 끝 점까지 도달 할 수 있는 경로의 수를 구하기.
목표 지점의 왼쪽까지 갈 수 있는 경로와 위쪽까지 갈 수 있는 경로의 합으로 답을 구할 수 있다.
문제에서는 격자의 크기를 면의 수로 표현하고 있지만 실제 처리는 모서리를 기준으로 하므로 1칸 더 크게 계산한다.

1	1	1
1	2	3
1	3	6

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

long long int Problem015(int width, int height) {     width++;     height++;       long long int** grid = new long long int *[width];     for (int i = 0; i < width; i++)     {         grid[i] = new long long int[height];     }       for (int i = 0; i < width; i++)     {         for (int j = 0; j < height; j++)         {             grid[i][j] = 0;         }     }     grid[0][0] = 1;       for (int i = 0; i < width; i++)     {         for (int j = 0; j < height; j++)         {             if (i != 0)             {                 grid[i][j] = grid[i][j] + grid[i - 1][j];             }             if (j != 0)             {                 grid[i][j] = grid[i][j] + grid[i][j - 1];             }         }     }       long long int ret = grid[width - 1][height - 1];     for (int i = 0; i < width; i++)     {         delete[] grid[i];     }     delete[] grid;     return ret; }