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

 

난이도 : 골II

풀이 시간 : 50분

알고리즘 유형 : DP

풀이 방법 : Left, Right, Up 비교 후 최대값 확인  

 

 

문제 링크

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

 

 

 

화성 탐사 로봇 문제

 

 

📋 문제 설명

NASA의 화성 탐사 로봇이 N×M 크기의 지형에서 가장 탐사 가치가 높은 경로를 찾아야 합니다.
로봇은 다음 규칙에 따라 움직입니다:

1. 움직일 수 있는 방향:
   
       ★  왼쪽, 오른쪽, 아래쪽으로 이동할 수 있습니다.
       ★  위로는 이동할 수 없습니다.
   
   
2. 탐사 가치:
   
       ★  각 칸에는 정수로 탐사 가치가 주어지며, 한 번 방문한 칸은 다시 방문하지 않습니다.
   
   
3. 목표:
   
       ★   좌측 상단 (1, 1)에서 시작해 우측 하단 (N, M)으로 이동하며, 탐사 가치의 합을 최대화합니다.

 

 

🌟 주의 사항

일단 N, M을 확인해보겠습니다. 

N, M 최대값은 1000 입니다.

즉 O(N * M) 이상으로는 코드를 작성하면 안됩니다!

(dfs, bfs -> 완전탐색 X)

 

 

🧠 문제 풀이

1. Dynamic Programming (DP):
   
       ★   dp[i][j]는 (i, j)까지 이동했을 때의 최대 탐사 가치를 저장합니다.
   
   
2. 3방향에서 오는 값 비교:
   
       ★   왼쪽 → 현재 칸
       ★   오른쪽 → 현재 칸
       ★   위쪽 → 현재 칸
   
   
3. 왼쪽, 오른쪽 경로를 별도로 계산:
   
       ★   한 행씩 처리하며, 왼쪽에서 오는 경로와 오른쪽에서 오는 경로를 각각 계산한 뒤,
              병합하여 최대값을 업데이트합니다.

 

🔎 예제 테스트

 

입력

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

 

풀이 과정

 

첫 번째 행

[10, 35, 42, 50, 63]

 

 

두 번째 행 

right =    [172, 104, 80, 158, 95 ]
left  =    [78,  102, 24, 113, 145]
dp    =    [172, 104, 80, 158, 145]

 

이 두번째 행과 같은 과정을 반복하면 마지막 값인 319 도출됩니다.

핵심은 left, right를 순회한 뒤 다시 right, left 의 최대값을 dp에 넣어주는 것입니다.

 

 

아래는 코드입니다.

#include <iostream>
#include <vector>

using namespace std;

int n, m;
int board[1001][1001];
int dp[1001][1001];

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

    cin >> n >> m;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> board[i][j];

	// 첫 번째 행 초기화
	dp[0][0] = board[0][0];

	for (int j = 1; j < m; ++j)
	    dp[0][j] = dp[0][j - 1] + board[0][j];

    // 각 행별로 최대 탐사 가치 계산
    for (int i = 1; i < n; ++i) 
    {
        // 왼쪽에서 오는 값 계산
        vector<int> left(m), right(m);

        left[0] = dp[i - 1][0] + board[i][0];

        for (int j = 1; j < m; ++j)
            left[j] = max(left[j - 1], dp[i - 1][j]) + board[i][j];

        // 오른쪽에서 오는 값 계산
        right[m - 1] = dp[i - 1][m - 1] + board[i][m - 1];

        for (int j = m - 2; j >= 0; --j)
            right[j] = max(right[j + 1], dp[i - 1][j]) + board[i][j];

        // 왼쪽과 오른쪽을 병합하여 dp 갱신
        for (int j = 0; j < m; ++j)
            dp[i][j] = max(left[j], right[j]);
    }

    // 결과 출력
    cout << dp[n - 1][m - 1] << "\n";

	return 0;
}