백준 - 22342번 : 계산 로봇 (C++)

풀이 방법 : DP

입력 값들중 최댓값을 저장 값으로 삼고 가중치를 더해 출력 값을 구하다보면 결국에는 입력값중 최댓값은 바로 직전 열에 있는 입력값들 중에서만 나온다는 것을 알 수 있다. 바로 직전 열들의 입력값들은 한칸 위, 같은 행, 한칸 아래에 있는 입력값들만 가능하므로 이들만 고려해주면 된다.

앞서 말한 내용대로 한 열씩 차례대로 저장 값들을 구해나가주면 된다.

#include <iostream>
#include <vector>

using namespace std;

int D[2001][2001] = {};
int Output[2001][2001] = {};
int Save[2001][2001] = {};

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

    int M, N;
    cin >> N >> M;
    
    for (int i = 0; i < N; ++i)
    {
        string Str;
        cin >> Str;

        for (int j = 0; j < M; ++j)
            D[i][j] = (int)Str[j] - (int)'0';
    }

    if (M == 1)
    {
        cout << 0;
        return 0;
    }

    for (int i = 0; i < N; ++i)
    {
        Output[i][0] = D[i][0];
    }

    int Max = 0;
    
    for (int j = 1; j < M; ++j)
    {
        for (int i = 0; i < N; ++i)
        {
            Save[i][j] = Output[i][j - 1];
            if (i - 1 >= 0)
            {
                Save[i][j] = max(Output[i - 1][j - 1], Save[i][j]);
            }

            if (i + 1 < N)
            {
                Save[i][j] = max(Output[i + 1][j - 1], Save[i][j]);
            }

            Output[i][j] = Save[i][j] + D[i][j];

            Max = max(Save[i][j], Max);
        }
    }

    cout << Max;
}