백준14430 - 자원 캐기

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

14430번: 자원 캐기

이차원 배열에서 갈 수 있는 방향이 아래와 오른쪽만 주어져서 다이나믹 프로그래밍을 이용하여 풀었다. 현재 칸으로 갈 수 있는 최대의 자원수를 먹어가면서 나아가면 된다.

#include <iostream>
#include <algorithm>
#define MAX 301
using namespace std;

int N, M;
int d[MAX][MAX] = {0,};
int mat[MAX][MAX] = {0,};

int main() {
    cin >> N >> M;
    for(int i = 1; i <= N; i++) {
        for(int j = 1 ; j <= M; j++) {
            cin >> mat[i][j];
        }
    }
    
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            d[i][j] = max(d[i][j], d[i - 1][j] + mat[i][j]); //위에서 접근
            d[i][j] = max(d[i][j], d[i][j - 1] + mat[i][j]); //왼쪽에서 접근
        }
    }
    
    cout << d[N][M]; //마지막 칸은 결론적으로 최대의 값을 같는다.
    return 0;
}