눈누난나

문제는 여기에서 풀 수 있습니다.

전형적인 DP문제입니다. 왼쪽 맨 위에서 오른쪽 맨 아래로 이동하는 경로에 포함된 사탕 개수의 최댓값을 구하면 되는 문제로 만약 준규가 이동할 수 있는 방향이 8방향이거나 4방향(동서남북)이라면 dfs를 통해 풀어야 할 것 같습니다.

하지만 이번 문제에서는 방향이 오른쪽 / 아래쪽 / 오른쪽 아래 대각선 으로 한정되어있으므로, DP를 통해 쉽게 풀 수 있습니다.

미로의 크기는 가로세로 최대 10^3이므로 모든 미로의 방을 탐색해도 10^6이기 때문에 시간 복잡도 측면에서 안전합니다(O(NM)).

미로의 방에 놓여져있는 사탕의 개수를 입력받을 때 마다 현재 위치로 올 수 있는 위치(왼쪽 / 위쪽 / 왼쪽 위 대각선) 중에서 가장 큰 값을 더해주는 식으로 DP식을 구성했습니다.

arr[i][j] += max(arr[i-1][j], max(arr[i][j-1], arr[i-1][j-1]));

속도를 빠르게 해보겠답시고 입력을 받으면서 DP연산을 해도 시간이 줄지를 않았습니다. 아무래도 상수만큼 시간을 줄이는 것은 크게 의미가 없는 것 같습니다.

소스코드:

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <unordered_set>
#include <cstring>
using namespace std;

int arr[1001][1001];

// main function
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> arr[i][j];
			arr[i][j] += max(arr[i - 1][j], max(arr[i][j - 1], arr[i - 1][j - 1]));
		}
	}

	cout << arr[N][M];

	return 0;
}