11048 이동하기

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int arr[1005][1005] = {0};
int dp[1005][1005] = { 0 };
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            scanf("%d", &arr[i][j]);
            
    dp[n][m] = arr[n][m];
    for (int i = n - 1; i >= 1; i--)
        dp[i][m] = arr[i][m] + dp[i + 1][m];
    for (int i = m - 1; i >= 1; i--)
        dp[n][i] = arr[n][i] + dp[n][i + 1];
 
    for (int i = n; i >= 1; i--) 
        for (int j = m; j >= 1; j--) 
            dp[i - 1][j - 1] = arr[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1]);
        
    printf("%d", dp[1][1]);
}