[백준 2169] 로봇 조종하기 (C++)

https://www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

문제

---

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

출력

---

첫째 줄에 최대 가치의 합을 출력한다.

 

문제 풀이

---

dp 문제.

3차원 배열을 이용하여 문제를 해결하였다.

dp[0][i][j]는 왼쪽에서 배열의 [i][j] 칸에 왔을 때의 값을 저장한 것이며, dp[1][i][j]는 위쪽에서 왔을 때, dp[2][i][j]는 오른쪽에서 왔을 때의 값을 저장한 것이라고 하자.

 

한 번 지난 칸은 다시 지나지 않으므로 왼쪽에서 와서 [i][j]칸에 도착했다면 [i][j-1] 칸은 이전에 오른쪽에서 온 것이 아니어야 한다. 따라서 dp[0][i][j]이 가질 수 있는 최대값은 dp[0][i][j-1]와 dp[1][i][j-1] 중 큰 값에 그 칸의 가치를 더한 것이다.

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

 

위쪽에서 와서 [i][j]칸에 도착했다면 [i-1][j]칸은 이전에 아무데서나 온 것이어도 상관이 없다.

즉, dp[1][i][j] = max({ dp[0][i - 1][j], dp[1][i - 1][j], dp[2][i - 1][j] }) + arr[i][j]이 성립한다.

 

오른쪽에서 와서 [i][j] 칸에 도착했다면 [i][j+1]칸은 이전에 왼쪽에서 온 것이 아니어야 한다.

따라서 dp[2][i][j] = max(dp[1][i][j-1], dp[2][i][j-1]) + arr[i][j] 라는 식이 성립한다.

 

이를 배열의 처음부터 끝까지 탐색하고 dp 배열에 저장하여 dp[N-1][M-1]의 3방향 중 가장 큰 값을 출력해주면 된다.

 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

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

	int N, M;
	cin >> N>>M;
	int** arr = new int*[N];
	int*** dp = new int**[3];
	for (int i = 0; i < 3; i++)
	{
		dp[i] = new int* [N];
		for (int j = 0; j < N; j++)
		{
			dp[i][j] = new int [M];
			for (int k = 0; k < M; k++)
			{
				dp[i][j][k] = -99999999;
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[M];
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
		}
	}
	dp[0][0][0] = arr[0][0];
	dp[1][0][0] = arr[0][0];
	dp[2][0][0] = arr[0][0];
	//0은 왼쪽, 1은 위쪽, 2는 오른쪽에서 온 것.
	for (int i = 1; i < M; i++)
	{
		dp[0][0][i] = dp[0][0][i - 1]+ arr[0][i];
	}
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			dp[1][i][j] = max({ dp[0][i - 1][j], dp[1][i - 1][j], dp[2][i - 1][j] }) + arr[i][j];
		}
		dp[0][i][0] = dp[1][i][0];
		dp[2][i][M - 1] = dp[1][i][M - 1];
		for (int j = 1; j < M; j++)
		{
			dp[0][i][j] = max(dp[0][i][j - 1], dp[1][i][j-1]) + arr[i][j];
		}
		for (int j = M - 2; j >= 0; j--)
		{
			dp[2][i][j] = max(dp[2][i][j + 1], dp[1][i][j + 1]) + arr[i][j];
		}
	}
	cout << max(dp[0][N - 1][M - 1], dp[1][N-1][M-1]) << "\n";
	return 0;
}