눈누난나

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

전형적인 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;
}

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

bfs를 쓸까 하다가 경로의 개수가 상당히 많아지는 것을 보고 dp를 써야겠구나 싶었습니다.

진행방향이 오른쪽이나 아래 뿐이므로, 순차적으로 가능성의 개수를 dp로 풀어나가면 됩니다. 

dp배열의 값을 [가능성의 개수]로 정의했기 때문에 초기값(dp[0][0])을 1로 설정하고 NXN배열을 순차적으로 탐색합니다. 탐색 방향과 점프 방향이 같으므로, 딱히 가지치기 할 케이스가 없습니다.

문제를 풀면서 신경써야했던 부분은 가장 오른쪽 아래 칸에서 dp연산을 수행하지 않는 것과 경로의 수가 int범위를 넘어가므로 dp배열을 long long으로 선언하는 것이었습니다.

시간복잡도는 O(N^2)이고 N<=100이므로 빠르게 문제를 풀 수 있었습니다.

#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[101][101];
long long dp[101][101];

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

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cin >> arr[i][j];
	}

	dp[0][0] = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (arr[i][j])
			{
				if (i + arr[i][j] < N)
					dp[i + arr[i][j]][j] += dp[i][j];
				if (j + arr[i][j] < N)
					dp[i][j + arr[i][j]] += dp[i][j];
			}
		}
	}

	cout << dp[N - 1][N - 1];

	return 0;
}