[C++] 백준 10164번 격자상의 경로

다이나믹 프로그래밍 문제입니다.

1번칸에서 N*M번 칸으로 갈때  O표시 되어있는 칸을 들려서
최소의 길로 갈 수 있는 경우의 수를 구하는 문제입니다.

1    2    3   4    5
6    7   (8)   9   10
11  12  13  14  15

다음과 같이 8번에 체크되어 있을 때
4, 5, 11, 12번은 체크할 필요가 없습니다.

O표시된 인덱스를 checkX, checkY로 했을 때
0,0~checkX,checkY와
checkX,checkY~n-1,m-1번의
길들만 0으로 입력해주어서 체킇하도록 합니다.

0,0 부터 DFS방식으로 아래와 오른쪽을 확인하고
DP의 값이
-1이면 패스하며,
1보다 높으면 그 값을 가져오고
0이면 탐색합니다.
이 방식을 통해 DP배열에 값을 저장해서
총 가능한 경우의 수를 구할 수 있습니다.

#include <iostream>
#include <cstring>
using namespace std;

int map[20][20];
int DP[20][20];
int checkX = -1;
int checkY;
int n, m;
int num;

int move(int x, int y)
{
	if (x == m - 1 && y == n - 1) {
		return 1;
	}
	if (DP[y][x] == -1) {	// 길이 없을 때
		return 0;
	}
	else if (DP[y][x] > 0) {	// 길이 있을 때
		return DP[y][x];
	}
	
	DP[y][x] += move(x + 1, y);
	DP[y][x] += move(x, y + 1);
	
	return DP[y][x];
}

int main(int argc, char *argv[])
{
	memset(map, 0, sizeof(map));
	memset(DP, -1, sizeof(DP));

	cin >> n >> m;
	cin >> num;

	checkX = (num - 1) % m;
	checkY = (num - 1) / m;

	if (checkX != -1) {
		for (int i = 0; i <= checkX; ++i) {
			for (int j = 0; j <= checkY; ++j)
				DP[j][i] = 0;
		}

		for (int i = checkX; i < m; ++i) {
			for (int j = checkY; j < n; ++j)
				DP[j][i] = 0;
		}
	}
	else {
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j)
				DP[j][i] = 0;
		}
	}

	move(0, 0);

	cout << DP[0][0] << endl;

	return 0;
}