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

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

 

난이도 : 골드 2 
알고리즘 유형 : DP 
풀이 시간 : 42분 

문제 풀이 

로봇은 두 가지 이동 조건을 갖고 있다.

1. 아래, 왼쪽, 오른쪽 방향으로만 갈 수 있다.
2. 한 번 방문한 곳은 다시 방문하지 않는다.

문제를 마주하고 가장 처음 생각할 수 있는 알고리즘은 그래프 탐색(BFS / DFS)이다. 하지만, N과 M의 범위가 $0 ≤ N, M ≤ 1000$이기 때문에 DFS로 접근할 경우, 시간초과가 발생하게 되고 BFS로 접근할 경우, 최댓값을 찾기에는 힘들다. 

문제를 다시 한 번 생각해보면, 위쪽 방향으로는 갈 수 없다고 한다. 다시말해, 이전 결과를 생각하지 않는다는 것이고, 이는 즉 DP로 해결이 가능하다는 소리이다.

 

아래로 이동할 때, 우리가 필요한 고정된 정보는 윗 줄의 최댓값 정보만 있으면 된다. 

따라서 다음 두 가지 경우로 경로의 값을 구한 뒤, 최댓값을 DP 배열에 저장하는 방식으로 진행하면 해결할 수 있다.

1. 왼쪽으로 이동해보며 이동값 업데이트
2. 오른쪽으로 이동해보며 이동값 업데이트

이후, 두 경로의 최댓값을 DP에 저장하면 된다.

문제에서 주어진 1번 예제에 대한 경로를 그림으로 나타내면 다음과 같다.

결국 파란색 라인이 최종 경로가 된다.

 

코드

/*
왼쪽, 오른쪽, 아래쪽으로는 이동 가능
한 번 탐사한 지역을 다시 탐사하지는 않음

풀이:
DP
오른쪽, 왼쪽 각각에서 온 값들 저장해두기
이후, dp에 왼쪽, 오른쪽의 최댓값 저장
*/

#include <iostream>
#include <algorithm>
#include <vector>
#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;

int n, m;
int arr[1001][1001];
int dp[1001][1001] = { 0, };

int main() {
	cin >> n >> m;
	vector<int> right(m + 1);
	vector<int> left(m + 1);
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < m + 1; j++)
			cin >> arr[i][j];
	}

	// 0. 첫번째 줄 초기화
	dp[1][1] = arr[1][1];
	for (int i = 2; i < m + 1; i++)
		dp[1][i] = dp[1][i - 1] + arr[1][i];

	// 1. DP 시작
	for (int i = 2; i < n + 1; i++) {
		// 왼쪽 오른쪽 나눠서 계산한 뒤에 합치기
		right[1] = dp[i - 1][1] + arr[i][1];
		left[m] = dp[i - 1][m] + arr[i][m];

		// 2. 오른쪽부터 먼저 채우기
		for (int j = 2; j < m + 1; j++)
			right[j] = max(right[j - 1], dp[i - 1][j]) + arr[i][j];
		// 3. 왼쪽 값 채우기
		for (int j = m - 1; j > 0; j--)
			left[j] = max(left[j + 1], dp[i - 1][j]) + arr[i][j];
		// 4. dp테이블 최댓값으로 업데이트
		for (int j = 1; j < m + 1; j++)
			dp[i][j] = max(left[j], right[j]);

		// 5. left, right 초기화
		for (int i = 1; i < m + 1; i++) {
			right[i] = 0;
			left[i] = 0;
		}
	}

	cout << dp[n][m] << '\n';

	return 0;
}

배운 점 

DP 문제는 알고리즘을 생각하기까지 아직도 시행착오가 존재하고, 바로바로 떠올리는게 쉽지 않아보인다. 하지만 여러 DP문제를 풀면서 들었던 생각은, 이전 결과에 영향을 미치지 않는다면 DP로 무조건 해결이 가능하다는 점이다. 이 부분을 엄두하여 문제를 풀어나가면 좋을 것 같다.&&