1520 : 내리막 길

풀이

메모이제이션 하면서 탐색해주자!!

코드

#include <stdio.h>

const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int n, m, a[505][505], d[505][505];

int dfs(int x, int y) {
	if (x == n && y == m) return 1;
	if (~d[x][y]) return d[x][y];
	d[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (a[nx][ny] && a[nx][ny] < a[x][y]) d[x][y] += dfs(nx, ny);
	}
	return d[x][y];
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
		scanf("%d", &a[i][j]), d[i][j] = -1;

	printf("%d\n", dfs(1, 1));

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-01-29 13:55

Read more posts by this author