이동하기

#include <iostream> #include <vector> #include <algorithm> using namespace std; int n, m; int map[1001][1001]; int dp[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } dp[0][0] = map[0][0]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (i == 0 && j == 0) continue; else if (i == 0) { dp[i][j] = dp[i][j - 1] + map[i][j]; } else if (j == 0) { dp[i][j] = dp[i - 1][j] + map[i][j]; } else dp[i][j] = max(dp[i - 1][j - 1] + map[i][j], max(dp[i - 1][j] + map[i][j], dp[i][j-1] + map[i][j])); } } cout << dp[n-1][m-1] << '\n'; return 0; }