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

문제

백준 11048

11048번: 이동하기

풀이

[i, j]에서 [i+1, j], [i][j+1], [i+1][j+1]로 이동할 수 있습니다.

[i+1][j+1]은 어차피 [i+1, j], [i][j+1]를 거쳐 이동할 수 있으므로 고려하지 않아도 됩니다.

(돌아서 갈 때 얻는 사탕이 무조건 크거나 같습니다.)

따라서 dp[i]j[j]에는 dp[i-1][j], dp[i][j-1] 중 더 큰 값에 map[i][j]를 더해준 값을 넣습니다.

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int map[1000][1000];
int dp[1000][1000];
int N, M;
int main()
{
    ios_base::sync_with_stdio(false);
    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[i][j] = map[i][j];
            if (i - 1 >= 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + map[i][j]);
            }
            if (j - 1 >= 0) {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + map[i][j]);
            }
        }
    }
    cout << dp[N - 1][M - 1];
    return 0;
}