[BOJ] (C++) 11048 이동하기

실버1 문제이며, 전형적인 DP문제이다.

현재의 pos는 그 전의 pos가 될 수 있는것 중 제일 큰 것을 받아오면 된다.

문제 링크 https://www.acmicpc.net/problem/11048

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M; cin >> N >> M;

	vector<vector<int>> maze(N + 1, vector<int>(M + 1));
	vector<vector<int>> DP(N + 1, vector<int>(M + 1));

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


	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			DP[i][j] = maze[i][j] + max(max(DP[i - 1][j], DP[i][j - 1]), DP[i - 1][j - 1]);

	cout << DP[N][M] << '\n';

	return 0;
}