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

www.acmicpc.net/problem/1520

1520번: 내리막 길

처음엔 그냥 DFS로 풀려고 했지만 계속 시간 초과가 나와서 고민을 많이 했다. 그냥 DFS를 사용하면 4^(500*500)번의 연산 횟수가 나온다는 것을 잘 몰랐다..

 

결국 풀다가 도저히 안되서 답을 보고 풀 수 있었는데 DP를 bottom up형식으로 써야하는 것이 어려웠던 문제이다.

 

문제 해설 중에는 이 블로그가 이해를 하는데 많이 도움을 준 것 같다.

wootool.tistory.com/83

[백준][1520번][DP] 내리막길

결국 내가 푼 코드는

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

int map[501][501];
int dp[501][501];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int m, n;

int dfs(int x, int y) {
	if (!x && !y) {
		return 1;
	}
	if (dp[x][y] == -1) {
		dp[x][y] = 0;
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i];
			int b = y + dy[i];
			if (a >= 0 && b >= 0 && a < m && b < n &&
				map[a][b] > map[x][y]) {
				dp[x][y] += dfs(a, b);
			}
		}
	}
	return dp[x][y];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(m-1, n-1);
	return 0;
}

DP를 이런식으로 사용할 수 도 있다는 것을 알 수 있었고 아직 부족함을 많이 느끼게 해준 문제였다.. ㅠㅠ