C++[백준]22342번 계산 로봇

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

22342번: 계산 로봇

 

솔루션

---

맞왜틀로 골머리를 앓았다. DP 문제인 건 알겠으나, 
r-1, c-1

r , c-1

r+1, c-1  중에서 최대 값을 저장 값으로 해 주었으나 어딜 틀렸는지 모르겠어 머리를 쥐어짜다 이리저리 수정하다 보니 성공했다.

 

일단 점화식이 다음과 같은 3가지 경우만 나눠지는 이유는

저장 값은 -1보다 더 이전 열에서 갖고 올 수 있지만 -1에서 더 이전의 열에서 가장 높은 저장 값을 가져와 저장 할 것이다.

그러면 이전 열의 값은 더 이전 열에서의 최대 저장 값 + 현재 가중치 까지 더한 것이 출력 값이 되기 떄문에 무조건 이전 열에서 가져오는 것이 더 이득이다. (다 양수이기 때문)

 

 

 

 

그런데 나는 기저 조건의 위치를 잘 못 적어서 틀렸었다..

 

 

코드

---

#include <iostream>
using namespace std;

int N, M;
string str[2002];
int arr[2002][2002];
int dp[2002][2002];

int solve(int r, int c) {
	if (r < 0 || c < 0 || r >= N) return 0;
	if (c == 0) return arr[r][c];
	if (dp[r][c]) return dp[r][c] + arr[r][c];

	int& ref = dp[r][c];
	int maxValue = max(solve(r, c - 1), solve(r - 1, c - 1));
	maxValue = max(maxValue, solve(r + 1, c - 1));
	ref = maxValue;
	return arr[r][c] + ref;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> str[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			arr[i][j] = str[i][j] - '0';
		}
	}

	int ans = -987654321;
	for (int i = 0; i < N; i++) {
		ans = max(ans, solve(i, M - 1) - arr[i][M - 1]);
	}

	cout << ans << '\n';
}