[백준] 1520-내리막 길(C++)

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

1520번: 내리막 길

 

dp라는걸 모르고 풀었음 더 어려웠을 문제였습니다. 
처음에 bfs 관점으로 접근하는데 자꾸 예외케이스가 생겼습니다.

예를 들어서, 단순히 오른쪽, 아래로만 이동하는게 아니라 위에 올라갔다가, 왼쪽으로 갔다가 올 수도 있기 때문입니다.

 
그래서 모든 경우를 탐색해주어야 한다고 인식하게 되었고, dp의 UP-DOWN 방식으로 구현을 하자는 아이디어를 얻었습니다.

 

점화식은 아래처럼 구현했습니다. 이때 ny, nx는 인접한 4방향 좌표를 모두 탐색합니다.

if (ny >= 1 && ny <= m && nx >= 1 && nx <= n) {
			if (arr[y][x] < arr[ny][nx]) {
				ret += solved(ny, nx);
			}
		}

 

 

 

아래는 전체 정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;
/*
	dp라고 모르고 풀었음 더 어려웠을 문제
	처음에 bfs 관점으로 접근하는데 자꾸 예외케이스가 생김
	모든 경우를 탐색해주어야 한다고 인식하게 됨 -> UP-DOWN 방식으로 구현
*/
int m, n;
int arr[501][501] = { 0, };
int dp[501][501] = { 0, };

int y_ar[4] = {0, 0, -1, 1};
int x_ar[4] = { 1,-1,0,0 };

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

	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (ny >= 1 && ny <= m && nx >= 1 && nx <= n) {
			if (arr[y][x] < arr[ny][nx]) {
				ret += solved(ny, nx);
			}
		}
	}

	return ret;
}

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

	cin >> m >> n;

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

	memset(dp, -1, sizeof(dp));
	cout << solved(m,n) << endl;

	/*
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}
	*/
	return 0;
}

dp라고 인식되는  순간 체감난이도가 확 줄었습니다.

이해가 안되시면 천천히 디버깅해보세요!