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

문제링크 : https://boj.kr/11048

위 그림과 같이 3방향으로 이동하면서 경로 상의 최대 값을 찾는 문제이다.

단계를 계속 진행해서 마지막까지 가게 되면 계산이 가능한 방향은 위 그림처럼 된다.

DP 식으로 표현해보면 다음과 같이 표현 가능하다.

DP[N][M] = MAX (DP[N-1][M], DP[N][M-1], DP[N-1][M-1]) + 자기자신값

// BOJ 11048 이동하기
#include <iostream>
#include <vector>
 
using namespace std;
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int max(int a, int b, int c) {
    return max(max(a, b), c);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int N, M, input;
    cin >> N >> M;
    vector<vector<int> > dp(N + 1, vector<int>(M + 1, 0));
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> input;
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + input;
        }
    }
    cout << dp[N][M];
 
    return 0;
}