백준 1520번: 내리막 길

[문제 링크]

1520번: 내리막 길

---

이 문제는 낮은 정답률에 비해 쉽게 풀 수 있었다.

정답률이 낮은 이유는 아마도 동서남북 방향을 탐색하지 않고 동쪽과 남쪽만 탐색해서 오답을 받는 경우가 많기 때문일거라 생각한다.

 

동서남북 방향을 탐색하여 높이가 낮은 지점이 있다면 그 지점에서 (M, N)으로 가는 경로의 개수를 구하고 그 값을 누적해주면 된다.

 

한 지점에서 (M, N)으로 가는 경로의 개수는 항상 같기 때문에 이를 메모이제이션해주면 중복탐색을 최소화할 수 있다.

---

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

int M, N, arr[501][501], memo[501][501];
int dy[4] = { 1,-1,0,0 }, dx[4] = { 0,0,1,-1 };

int Topdown(int hereY, int hereX)
{
	if (hereY > M || hereY == 0 || hereX > N || hereX == 0)
		return 0;
	if (hereY == M && hereX == N)
		return 1;

	int& ret = memo[hereY][hereX];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 0; i < 4; i++)
		if (arr[hereY][hereX] > arr[hereY + dy[i]][hereX + dx[i]])
			ret += Topdown(hereY + dy[i], hereX + dx[i]);

	return ret;
}

int main(void)
{
	cin >> M >> N;

	for (int i = 1; i <= M; i++)
		for (int j = 1; j <= N; j++)
			cin >> arr[i][j];

	memset(memo, -1, sizeof(memo));
	cout << Topdown(1, 1) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 88 day