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

문제

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

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

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

입력

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

출력

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

 

<DP코드>

#include<stdio.h>
#include<algorithm>
using namespace std;
/*
5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15
*/
int N, M;
int map[1001][1001];
int dp[1001][1001];
int Right[1001];
int Left[1001];

int main(void)
{
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			scanf("%d", &map[i][j]);
		
	
	dp[0][0] = map[0][0]; // 시작값

	for (int j = 1; j < M; j++) // 맨 윗줄 dp 생성
		dp[0][j] += dp[0][j - 1] + map[0][j];


	for (int i = 1; i < N; i++)
	{
		// 맨 왼쪽 = > 오른쪽으로 검사
		Right[0] = dp[i - 1][0] + map[i][0];
		for (int j = 0; j < M - 1; j++)
			Right[j + 1] = max(Right[j], dp[i - 1][j + 1]) + map[i][j + 1];

		// 맨 오른쪽 = > 왼쪽으로 검사
		Left[M - 1] = dp[i - 1][M - 1] + map[i][M - 1];
		for (int j = M - 2; j >= 0; j--)
			Left[j] = max(Left[j + 1], dp[i - 1][j]) + map[i][j];

		// Right배열과 Left배열중 큰 값 dp에 저장
		for (int k = 0; k < M; k++)
			dp[i][k] = max(Right[k], Left[k]);
	}

	printf("%d", dp[N - 1][M - 1]);

}

 

위의 풀이법 예시로 들자면 아래와 같은 4x4 배열이 있다고 가정을 하자.

<map배열>

1	2	3	-1
-2	-3	4	5
6	-2	-4	-2
-1	3	2	3

 

1. DP배열에서 맨 윗줄의 가치만을 더하기

1	3	6	5

 

2. Right배열, Left배열 각각 만들기

<Right배열> (map배열에서 왼쪽값과 위의 값을 비교해서 큰값을 저장 )

-> -> -> -> -> -> -> -> -> ->

-1

0

10

15

<Left배열> (map배열에서 오른쪽값과 위의 값을 비교해서 큰값을 저장 )

<- <- <- <- <- <- <- <- <- <- 

9

11

14

10

 

3. Right배열과 Left배열에서 max값만 추출하여 DP 배열에 저장하기

1	3	6	5
9	11	14	15

 

4. 위의 과정 반복 후 DP[N-1][M-1] 값을 printf하면 정답 도출!

 

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

2169번: 로봇 조종하기