백준 11048 C++ - 이동하기

Intro

문제해결 및 소스코드

• 처음에 문제를 보고 DFS로 풀어봤다. 하지만 시간초과가 발생했다.

• 문제를 다시한번 풀어써보고, DP로 풀어보기로했다.

• 예시로, 이 문제는 미로의 (1,1)부터 시작하여 (3,4)까지 가면서, 각 미로좌표의 숫자(사탕수)를 더해나가며

• 목적지(3,4)에 도달했을 때 더해진 숫자의 최대값을 구하는 문제이다.

• 특징은 나아갈 수 있는 방향이 반드시 우하향 이라는것이다.

• 예를들어, (2,2)에서의 최대 사탕갯수는 몇개일까?
  • (2,2)를 가는 방법은 그림에서와 같이 3가지이다.
  • 따라서 3가지 경로중 최대값을 (2,2)에 작성해주면 된다.
• maxCandies라는 배열을 만들어, 여기에 각 좌표까지에서 획득할 수 있는 최대 사탕수를 저장했다.

#include <iostream>
#include <algorithm>

using namespace std;

int maxCandies[1001][1001];	
int maze[1001][1001];

int main()
{
	int n, m;
	cin >> n >> m;

	// 입력
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			cin >> maze[i][j];
		}
	}

	// DP동작
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			// 우->하, 하->우, 대각선 방향으로 탐색하는것 중 가장큰 값
			maxCandies[i][j] = max(max(maxCandies[i][j - 1], maxCandies[i - 1][j]), maxCandies[i - 1][j - 1]) + maze[i][j];
		}
	}

	cout << maxCandies[n][m];
}