[백준] 11048 - 이동하기

전형적인 DP문제

입력을 받으며 DP배열의 (r - 1, c), (r, c - 1), (r - 1, c - 1) 중 가장 큰값을 현재 입력되는 위치의 사탕개수를 더해주면 끝

#include <iostream>
#define MXSIZE 1002
#define MAX(X, Y) (X) > (Y) ? (X) : (Y)
using namespace std;
 
int map[MXSIZE][MXSIZE], dp[MXSIZE][MXSIZE];
int    N, M;
 
int main(void)
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            cin >> map[i][j];
            dp[i][j] = MAX(dp[i - 1][j - 1], MAX(dp[i - 1][j], dp[i][j - 1]));
            dp[i][j] += map[i][j];
        }
    cout << dp[N][M] << endl;
    return 0;
}