BOJ 2169 : 로봇 조종하기 [C++]

 

2169번: 로봇 조종하기

 

그냥 아래, 오른쪽만 갈 수 있었으면 묻지도 따지지도 않고 'DP구만'하고 풀었겠지만,

왼쪽으로도 갈 수 있다는 조건 때문에 DP를 사용하되, 어떻게 풀이할까 고민했다.

 

DP 배열을 주어지는 지형과 같이 2차원으로 구성할까 했지만 각 방향에서 해당 칸으로 오는 경우들을 고려하기 위해서

3차원 배열로 구성했다.

 

int dp[1002][1002][3]; // from left, from up, from right

지형의 탐사 가치가 음수인 경우가 있으니, DP 배열을 임의의 큰 음수 값으로 초기화해 주자.

 

 

{i, j}에 도달하는 세 가지 경우를 살펴보자.

 

1번, 왼쪽(i, j - 1)에서 오는 경우.

이 경우 → → , ↓ →(로봇이 아래로 내려간 다음, 오른쪽으로 이동) 이렇게 이동해서 오는 두 가지 경우가 있다.

 

2번, 위(i - 1, j)에서 오는 경우.

이 경우 → ↓, ↓ ↓, ← ↓(로봇이 왼쪽으로 이동한 다음, 아래로 이동) 이렇게 이동해서 오는 세 가지 경우가 있다.

 

3번, 오른쪽(i, j + 1)에서 오는 경우.

이 경우 ← ←, ↓ ←(로봇이 아래로 내려간 다음, 왼쪽으로 이동) 이렇게 이동해서 오는 두 가지 경우가 있다.

 

오른쪽에서 오는 경우는 좀 제한적이다.

1. 첫 번째 행과 마지막 행은 오른쪽에서 오는 경우를 구하지 않아도 된다.

     ({1, 1}에서 출발하기 때문에 첫 번째 행은 어디든 오른쪽에서 올 수 없고, 마지막 행은 {N, M}에 도달해야 하기 때문.)

2. ↓ ← 이렇게 오는 경우(from dp[i][j + 1][1])때문에, {i, j + 1}의 dp 값을 미리 구해놔야 한다.

    그러니 왼쪽, 위에서 오는 경우를 구해두고, 오른쪽에서 오는 경우를 구하자.

 

 

코드

#include <iostream>

int N, M;
int map[1002][1002];
int dp[1002][1002][3]; // from left, from up, from right

int main() {
    std::cin >> N >> M;

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

    std::fill_n(&dp[0][0][0], 1002 * 1002 * 3, -987654321);
    dp[1][1][0] = map[1][1];
    dp[1][1][1] = map[1][1];
    dp[1][1][2] = map[1][1];
    for (int i = 1; i < N + 1; i++) {
        for (int j = 1; j < M + 1; j++) {
            if (i == 1 && j == 1) {
                continue;
            }
            dp[i][j][0] = std::max(dp[i][j - 1][0], dp[i][j - 1][1]) + map[i][j];
            dp[i][j][1] = std::max(dp[i - 1][j][0], std::max(dp[i - 1][j][1], dp[i - 1][j][2])) + map[i][j];
        }
        if (i >= 2 && i < N) {
            for (int j = M; j > 0; j--) {
                dp[i][j][2] = std::max(dp[i][j + 1][1], dp[i][j + 1][2]) + map[i][j];
            }
        }
    }

    std::cout << std::max(dp[N][M][0], std::max(dp[N][M][1], dp[N][M][2]));
    return 0;
}