백준 1520, 내리막 길

문제

https://www.acmicpc.net/problem/1520

풀이

처음에는 이걸 그래프로 변환해서 내려오면서 dp를 할까했는데 이게 그래프로 만들기 너무 귀찮고 그럴만한 문제도 아닌 것 같아서 안했다.

다시 곰곰히 생각해보니까 시작점에서 상향식으로 하기에는 큐?로 하는 것 같은데 순서를 잘 모르겠어서 생각하기 쉬운 하향식으로 했다.

그냥 도착점부터 갈 수 있을 길을 되짚어 가면서 구하면 잘 생각해보면 아주 쉽게 구해진다.

다만 0으로 초기화 하고 나서 visit을 사용하지 않았더니 시간 초과가 났다 -1로 초기화 하니까 틀리길래 그냥 0 사용하고 visit 사용해서 풀었다.

근데 다시보니까 그래프도 적혀있는 것을 보면 되는 것 같다. 하지만 딱히 귀찮게 그렇게 하고 싶진 않다.

실수

• 요새 계속 딴길로 새는 것 같다. 그러지 말자. 기본을 적용해보고 안되면 그 다음으로 생각하자.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<vector<int>> memo(550, vector<int>(550, 0));
vector<vector<int>> cost(550, vector<int>(550, 0));
vector<vector<int>> visit(550, vector<int>(550, 0));
vector<pair<int, int>> dir(4, make_pair(0, 0));

int m, n;

int dp(int row, int col) {

	int res = 0;

	if (memo[row][col] != 0 || visit[row][col] == 1)
		return memo[row][col];

	visit[row][col] = 1;

	for (int i = 0; i < 4; i++) {

		if (1 <= row + dir[i].first && row + dir[i].first <= m) {

			if (1 <= col + dir[i].second && col + dir[i].second <= n) {

				if (cost[row][col] < cost[row + dir[i].first][col + dir[i].second])
					res += dp(row + dir[i].first, col + dir[i].second);

			}

		}

	}

	memo[row][col] = res;

	return res;

}

int main() {

	dir[0].first = 1;
	dir[0].second = 0;
	dir[1].first = 0;
	dir[1].second = 1;
	dir[2].first = -1;
	dir[2].second = 0;
	dir[3].first = 0;
	dir[3].second = -1;

	scanf("%d %d", &m, &n);

	for (int i = 1; i <= m; i++) {

		for (int j = 1; j <= n; j++) {

			scanf("%d", &cost[i][j]);

		}

	}

	memo[1][1] = 1;

	printf("%d", dp(m, n));

	return 0;

}