[백준] 2169. 로봇 조종하기 - C++

[Gold II]

 

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

 

풀이

일반적인 Bottom-Up 형식으로 풀어낸 DP 문제.

아래, 오른쪽으로만 갈 수 있는 것이 아닌, 왼쪽으로도 갈 수 있기 때문에 이를 고려해줘야 했으나,

"한 번 방문한 곳은 다시 방문하지 않는다" 라는 조건이 있기 때문에,

각 줄에서, 왼쪽부터 DP 배열을 갱신하고 (line 43~45), 또 오른쪽부터 다른 DP배열을 갱신한 후 (line 47~49),

둘 중 더 큰 것(최댓값)을 택하여 DP 배열을 최종적으로 갱신해주는 식으로 모든 줄을 반복하면 된다.

 

다만 주의할 것은, DP 배열을 초기화할 때, 음수 value값이 있으므로, 최댓값을 구하기 위해서는 0으로 초기화하지 않고, 나올 수 있는 가장 작은 값(-200,000 이하) 정도로 초기화할 것.

또한, (1, 1)에서 무조건 시작하므로, 첫째 줄은 왼쪽에서 오른쪽으로 밖에 갈 수 없으므로, 따로 처리해줄 것.

 

AC.

#include <algorithm>
#include <iostream>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);

typedef long long ll;
using namespace std;
const int MIN = -2e5 - 5;

int v[1002][1002];
int dp[1002][1002];
int dp2[1002][1002];

int main() {
    init;

    int N, M;
    cin >> N >> M;

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

    fill(&dp[0][0], &dp[N + 1][M + 1], MIN);
    fill(&dp2[0][0], &dp2[N + 1][M + 1], MIN);
    dp[0][1] = 0;
    dp[1][0] = 0;
    dp2[0][1] = 0;
    dp2[1][0] = 0;

    // [1][1]부터 시작하므로, 1행은 무조건 왼쪽부터 채워나가야 함
    for (int j = 1; j < M + 1; j++) {
        dp[1][j] = dp[1][j - 1] + v[1][j];
        dp2[1][j] = dp2[1][j - 1] + v[1][j];
    }

    for (int i = 2; i < N + 1; i++) {
        // 왼쪽부터 채우기
        for (int j = 1; j < M + 1; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + v[i][j];
        }
        // 오른쪽
        for (int j = M; j > 0; j--) {
            dp2[i][j] = max(dp2[i - 1][j], dp2[i][j + 1]) + v[i][j];
        }

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

    cout << dp[N][M];
}