#include <iostream>
using namespace std;
int a[1001][1001];
int d[1001][1001];
int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    d[1][1] = a[1][1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (d[i][j + 1] < d[i][j] + a[i][j + 1])
            {
                d[i][j + 1] = d[i][j] + a[i][j + 1];
            }
            if (d[i + 1][j + 1] < d[i][j] + a[i + 1][j + 1])
            {
                d[i + 1][j + 1] = d[i][j] + a[i + 1][j + 1];
            }
            if (d[i + 1][j] < d[i][j] + a[i + 1][j])
            {
                d[i + 1][j] = d[i][j] + a[i + 1][j];
            }
        }
    }

    cout << d[n][m];
    return 0;
}

나는 DP 가 너무 약하다.. 그래서 일단 저번에 풀던걸 복습하는 겸 풀어보았다.

문제 접근

위치를 (r,c) 라고 했을때, (r,c+1) , (r+1,c) , (r+1, c+1) 방향으로 이동하며 각 칸에 적힌 수를 얻을 수 있다. 위치 (n,m) 에 있을 때 얻을 수 있는 최대 합을 구하시오.

해결 방법

• (1,1) ~~~> (i,j) 으로 갈때, (i,j) 를 도착지점으로 놓아서 이전의 경로를 살펴보는 방법
• (1,1) ~~~> (i,j) 으로 갈때, (i,j) 를 시작지점으로 놓아서 다음의 경로를 찾는 방법

으로 구분할 수 있는데, 나는 후자의 방법을 선택하였다.
d[i][j] = i,j 에 위치할때 놓을 수 있는 가장 큰 값.
d[1][1] 은 정해져있는 것이므로 a[1][1]으로 초기화 해준다.
그리고 다음의 경로를 갈때 어떤 방법으로 갈지 업데이트 해준다.
d[i+1][j] = max( d[i+1][j] , d[i][j] + a[i+1][j])
d[i+1][j+1] = max( d[i+1][j+1], d[i][j] + a[i+1][j+1])
d[i][j+1] = max( d[i][j+1], d[i][j] + a[i][j+1])