백준, BOJ, 11048번, 이동하기 : C++ [CPP]

이것 내가 현재 칸에 있다면 어떤 칸을 거쳐서 오는 것이 좋은가?

어느 칸에서 올 수 있는가?

현재 칸을 오면 사탕개수가 어떻게 되는가?

를 생각하자

 

 

 

https://www.acmicpc.net/problem/11048

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1001;

int  N, M;

int map[MAX][MAX];
int dp[MAX][MAX];

int main() {
    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }


    //초기 값 1행과 1열 값 초기화 (0행, 0열의 성분은 0임)
    dp[1][1] = map[1][1];
    //1행
    for (int i = 2; i <= M; i++) {
        dp[1][i] += dp[1][i - 1] + map[1][i];
    }
    //1열
    for (int i = 2; i <= N; i++) {
        dp[i][1] += dp[i - 1][1] + map[i][1];
    }

    for (int i = 2; i <= N; i++) {
        for (int j = 2; j <= M; j++) {
            dp[i][j] = max({ dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]}) + map[i][j];
        }
    }
    /*
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cout << dp[i][j] << " ";
        }
        cout << '\n';
    }
    */

    cout << dp[N][M];

    return 0;
}