프로젝트 오일러 문제 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

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;
}