BOJ #11048

문제

문제 접근

가장 최대가 되는 경로를 누적하면서 가야하기 때문에,
다이나믹 프로그래밍을 이용하였다. 사실상, r+1 또는 c+1를 한번 지나는게
대각선으로 이동하는 것보다 사탕을 같거나 더 많이 획득할 수 있으므로
비교하지 않아도 된다.

따라서, (r,c)를 기준으로 r-1의 지점과
c-1의 지점 중 어디를 지나야 최대로 획득할 수 있는지만 구하고,
최대 누적 합을 계속해서 저장해주면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
#include <sstream>
#include <math.h>
#define endl '\n'

using namespace std;
typedef long long ll;

ll board[1005][1005];
ll dp[1005][1005] = {0, };
int n, m;

int main(int argc, const char * argv[]){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(nullptr);
    
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> board[i][j];

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            
            // * 대각선은 생각할 필요없음, 최대가 될수 없음 *
            dp[i][j] = board[i][j] + max(dp[i-1][j], dp[i][j-1]);
        }
    }

    
    cout << dp[n][m] << endl;
    return 0;
}