Solution

• dp배열을 3차원 배열로 선언하였다. 해당 이유는 위, 왼쪽, 오른쪽에서 오는 값들을 저장하기 위해서이다. 점화식에 대해서 얘기하자면,밑의 식과 같다.

  dp[0][i][j] = max(dp[0][i-1][j], dp[1][i-1][j], dp[2][i-1][j]) + arr[i][j]
  dp[1][i][j] = max(dp[1][i][j-1], dp[0][i][j-1]) + arr[i][j]
  dp[2][i][j] = max(dp[2][i][j+1], dp[0][i][j+1]) + arr[i][j]

• 즉 위에서 내려오는 값은 항상 배열의 i-1번째 인덱스의 최댓값이 된다.

• 하지만, 왼쪽에서 오는 값은 이전 인덱스의 위에서 내려오는 값(dp[0][i][j-1])과 이전 인덱스의 왼쪽에서 계속 오는 값(dp[1][i][j-1])의 최댓값이 된다. 오른쪽에서 오는 값도 이와 같은 방식으로 해결 할 수 있다.

• 글로 풀어쓰면 복잡해 보일 수 있으나, 코드로 보면 쉽게 이해가 된다.

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <string>
#include <stack>
#include <list>
#include <unordered_set>
#include <sstream>
#include <deque>
#include <math.h>
#include <map>
#include <set>

using namespace std;

int N, M;
long long arr[1001][1001];
long long dp[3][1001][1001];
int visited[1001][1001];

void Solution()
{
    dp[1][1][1] = arr[1][1];
    dp[2][1][1] = arr[1][1];
    dp[0][1][1] = arr[1][1];
    for(int i =2 ; i<=M; i++){
        dp[1][1][i]=  dp[1][1][i-1] + arr[1][i];
    }

    for(int i= 2; i<=N; i++){
        for(int j= 1; j<=M ;j++){
            dp[0][i][j] = max(dp[0][i][j], dp[1][i-1][j] + arr[i][j]);
            dp[0][i][j] = max(dp[0][i][j], dp[2][i-1][j] + arr[i][j]);
            dp[0][i][j] = max(dp[0][i][j], dp[0][i-1][j] + arr[i][j]);
        }
        for(int j = 1; j<=M; j++){
            dp[1][i][j] = max(dp[1][i][j], dp[1][i][j-1] + arr[i][j]);
            dp[1][i][j] = max(dp[1][i][j], dp[0][i][j-1] + arr[i][j]);
        }
        for(int j = M; j>=0; j--){
            dp[2][i][j] = max(dp[2][i][j], dp[2][i][j+1] + arr[i][j]);
            dp[2][i][j] = max(dp[2][i][j], dp[0][i][j+1] + arr[i][j]);
        }
    }
 
    cout <<  max(dp[0][N][M],max(dp[1][N][M],dp[2][N][M]));
}

void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> arr[i][j];

        }
    }
    for(int i = 0 ; i<=N+1; i++){
        for(int j =0 ; j<=M+1; j++){
            dp[0][i][j] = INT_MIN;
            dp[1][i][j] = INT_MIN;
            dp[2][i][j] = INT_MIN;
        }
    }
}

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

    Input();
    Solution();
}