[백준/C++] 이동하기_11048

📝 문제

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

💻 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <typeinfo>
#include <string>

using namespace std;
int n, m;
int dp[1001][1001];
int MAP[1001][1001];

int dfs(int row, int col) {

	if (dp[row][col] != -2134567890) {
		return dp[row][col];
	}

	if (row == n && col == m) {
		dp[row][col] = MAP[row][col];
		return MAP[row][col];
	}

	int dr[] = { 0, 1, 1 };
	int dc[] = { 1, 0, 1 };
	int maxValue = -2134567890;

	for (int i = 0; i < 3; i++) {
		int nr = row + dr[i];
		int nc = col + dc[i];
		if (nr <= 0 || nc <= 0 || nr > n || nc > m) continue;
		//if (dp[nr][nc] == -2134567890) continue;

		int next = dfs(nr, nc);

		maxValue = max(maxValue, next);
	}
	
	
	int nowValue = maxValue + MAP[row][col];
	dp[row][col] = nowValue;
	return nowValue;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = -2134567890;
		}
	}

	cout << dfs(1, 1);

	
	return 0;
}

💡 Point

dp문제로 top-down 방식으로 dfs로 풀었다.
MAP을 입력받을 때 시작좌표를 (0, 0)으로 받아버려서 값이 계속 다르게 나왔다...