<Baekjoon> #11048 Dynamic Programming_이동하기 c++

#11048 이동하기

각 정점에서 최대로 가져올 수 있는 사탕의 개수를 구해서 (n,m)까지 이르렀을 때 저장된 최댓값을 return 하면 된다. 사탕의 개수는 (1,1)부터 (n,m)까지 저장되어 있기 때문에 위에서 부터 top-down 방식으로 memoization 기법을 사용한다.

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 1001;
int maze[MAX][MAX];
int dp[MAX][MAX];
int n, m;

void countCandy() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int sum = max({ dp[i-1][j-1], dp[i-1][j], dp[i][j-1] });
			dp[i][j] = sum + maze[i][j];
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> maze[i][j];
	countCandy();
	cout << dp[n][m] << endl;
	return 0;
}