[C++][백준 11048] 이동하기

문제

접근 방법

특정 지점 r, c에서의 최대는 해당 지점으로 올 수 있는 (r-1, c), (r, c-1), (r-1, c-1)중에서 가장 큰 값을 가지는 것이다.

좌측 위에서 우측 아래로 단방향으로 정해져있기에 다이나믹 프로그래밍을 활용하면 해결할 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> maze, dp;
int N, M;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> M;
    maze = dp = vector<vector<int>>(N, vector<int>(M));
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> maze[i][j];
        }
    }

    // 0인 경우에는 특정 위치를 확인할 수 없다.
    dp[0][0] = maze[0][0];
    for (int i = 1; i < N; ++i)
    {
        dp[i][0] = maze[i][0] + dp[i - 1][0];
    }
    for (int i = 1; i < M; ++i)
    {
        dp[0][i] = maze[0][i] + dp[0][i - 1];
    }

    for (int i = 1; i < N; ++i)
    {
        for (int j = 1; j < M; ++j)
        {
            dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + maze[i][j]; // (r+1, c), (r, c+1), (r+1, c+1)
        }
    }
    cout << dp[N - 1][M - 1];
    return 0;
}

풀이

1000^2는 크지 않기에 문제없다.
보통 이런 문제를 만나면 나의 경우에는 0인 경우를 따로 해결해 주는데 굳이 그러지 않고 dp의 크기를 N+1, M+1로 하여서 1부터 시작해 줘도 된다.