[백준][C++] 1520: 내리막 길

문제 링크: https://www.acmicpc.net/problem/1520

 

다이나믹 프로그래밍 문제입니다. 뭔가 딱 봐도 BFS로 풀면 풀릴 것처럼 생겼지만 배열 크기가 커지면 경로 수도 엄청 늘어나기 때문에 한계가 있습니다.

바텀업 dp로 풀려고 머리를 좀 굴려봤는데 잘 안됩니다. 탑다운으로 풀었더니 단순하게 풀립니다. 왜 갑자기 이 문제만 바텀업으로 풀고싶어진건지;

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

int m, n;
int arr[500][500];
int dp[500][500];

int solve(int y, int x) {
	auto& ret = dp[y][x];
	if (ret != -1) return ret;
	ret = 0;

	if (y > 0 && arr[y][x] < arr[y - 1][x])
		ret += solve(y - 1, x);
	if (x<n - 1 && arr[y][x] < arr[y][x + 1])
		ret += solve(y, x+1);
	if (y<m - 1 && arr[y][x] < arr[y + 1][x])
		ret += solve(y + 1, x);
	if (x > 0 && arr[y][x] < arr[y][x - 1])
		ret += solve(y, x - 1);

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> m >> n;
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j)
			cin >> arr[i][j];

	memset(dp, -1, sizeof(dp));
	dp[0][0] = 1;
	cout << solve(m-1, n-1) << '\n';
	
	return 0;
}

(m-1, n-1)부터 시작해서 (0, 0)까지 거꾸로 올라가게 하거나 아님 반대로 해도 됩니다. 어쨌든 핵심은 dp입니다

dp배열 -1로 초기화하는 것과 시작점 or 도착점에 dp값을 1로 넣어주는걸 잊지 마세요