백준 2169 - 로봇 조종하기

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N x M의 크기로 화성의 모습이 주어진다.

각 칸에는 탐사 가치가 저장되어 있고 (1, 1)에서 출발하여 (N, M)에 도착할 때 최대 가치를 출력하는 것이다.

이때, 이동할 수 있는 방향은 왼쪽, 오른쪽, 아래쪽이다.

 

해당 문제는 dp로 해결할 수 있다.

문제에서 이동 방향이 총 세 가지이지만 이해를 위해 두 가지 경우로 줄여보자.

오른쪽과 아래쪽으로만 이동이 가능하다고 가정해 보자.

빨간색으로 칠해진 칸에 도착하기 위해서는 화살표가 시작된 칸에서 출발해야만 한다.

즉, 빨간칸까지의 최댓값은 화살표가 시작된 칸의 최댓값에 24를 더한 값과 같다.

dp[1][1] = Mars[1][1];
for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= M; j++)
    {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + Mars[i][j];
    }
}

 

 

그렇다면 이를 문제에 적용하면 다음과 같다.

화살표가 오른쪽에하나 더 추가된 것이다.

오른쪽에서 출발한 화살표는 몇 가지 예외가 존재한다.

오른쪽 칸에 도착하기 위해서는 위칸에서 오른쪽으로 이동한 경우가 존재해야 한다는 것이다.

즉, (1, 1)에서 출발하기 때문에 첫 줄은 절대 오른쪽에서 출발하는 화살표를 가질 수 없다.

또한, 마지막 줄에서도 (N, M)에 도착하기 때문에 오른쪽으로 진행하는 것은 의미가 없다.

 

이를 유의하고 기본적인 로직을 구성해 보자.

빨간 칸에 도착하기 위해서는 왼쪽, 오른쪽, 위쪽 총 세 가지 경우에서 접근할 수 있다.

하지만, 자세히 생각해 보면 총 네가지 경우가 된다.

왼쪽, 오른쪽, 왼쪽에서 접근한 위쪽, 오른쪽에서 접근한 위쪽 이렇게 총 네 가지이다.

왼쪽에서 접근한 위쪽과 오른쪽에서 접근한 위쪽을 분리한 이유는 빨간 칸 위쪽을 어디서 접근했는지에 따라 최댓값이 달라지기 때문이다.

빨간 칸의 윗줄이 가장 첫 줄이라 오른쪽에서 접근할 수 없지만 가능하다고 가정하면 다음과 같다.

• 왼쪽에서 접근: 10 + 68
• 오른쪽에서 접근: 10 + 25 + 7 + ... + (-78)
• 왼쪽 위에서 접근: 10 + 25
• 오른쪽 위에서 접근: 10 + ... + 7 + 25

빨간 칸의 윗줄이 첫 줄이라 예시가 조금 이상하지만 결론적으로는 윗 칸을 어디서 접근했는지에 따라 최댓값이 달라지기 때문에 한 번 더 비교해 주어야 한다는 뜻이다.

 

정리하자면, 왼쪽과 오른쪽에서 접근하는 최댓값을 메모이제이션하여 dp를 진행한다.

(1, 1)에서 출발하기 때문에 첫 줄은 오른쪽으로 접근하는 것이 불가능하므로 왼쪽과 오른쪽이 동일하다.

이후, 왼쪽은 자신의 왼쪽과 위쪽을 비교한 뒤, 오른쪽에서 접근한 위쪽을 한 번 더 비교해 준다.

오른쪽은 자신의 오른쪽과 위쪽을 비교한 뒤, 왼쪽에서 접근한 위쪽을 한 번 더 비교해 준다.

마지막 줄은 오른쪽에서 접근하는 것이 불가능하므로 정답은 왼쪽에서 접근하여 (N, M)에 도착한 값이 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, M;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N >> M;

    vector<vector<int>> dpLeft(N + 1, vector<int>(M + 1, -100));
    vector<vector<int>> dpRight(N + 1, vector<int>(M + 1, -100));
    vector<vector<int>> Mars(N + 1, vector<int>(M + 1, 0));

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> Mars[i][j];
        }
    }

    //first row
    dpLeft[1][1] = Mars[1][1];
    dpRight[1][1] = Mars[1][1];
    for (int j = 2; j <= M; j++)
    {
        dpLeft[1][j] = dpLeft[1][j - 1] + Mars[1][j];
        dpRight[1][j] = dpRight[1][j - 1] + Mars[1][j];
    }

    for (int i = 2; i <= N; i++)
    {
        //Left
        dpLeft[i][1] = max(dpLeft[i - 1][1], dpRight[i - 1][1]) + Mars[i][1];
        for (int j = 2; j <= M; j++)
        {
            int temp = max(dpLeft[i - 1][j], dpLeft[i][j - 1]);
            temp = max(temp, dpRight[i - 1][j]) + Mars[i][j];
            dpLeft[i][j] = temp;
        }

        //Right
        dpRight[i][M] = max(dpRight[i - 1][M], dpLeft[i - 1][M]) + Mars[i][M];
        for (int j = M - 1; j > 0; j--)
        {
            int temp = max(dpRight[i][j + 1], dpRight[i - 1][j]);
            temp = max(temp, dpLeft[i - 1][j]) + Mars[i][j];
            dpRight[i][j] = temp;
        }
    }

    cout << dpLeft[N][M];

    return 0;
}

---