[DP] BOJ 2169 로봇 조종하기

문제 링크 : www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

2차원 배열 형태의 입력에서 목적지까지의 최대 가치를 구하는 문제이다.

문제에서 로봇은 위쪽으로 이동할 수 없다는 것에 주목하자.

로봇이 위쪽으로 이동할 수 없기 때문에, 어떤 한 행에 대한 최대 가치를 구하기 위해 그 이전 행의 최대 가치들을 미리 구해놓는다는 접근이 가능하다.

 

또한 로봇은 오른쪽, 왼쪽 양방향으로 이동 가능하며, 한번 지난 칸은 이동할 수 없다는 제약을 갖고 있다.

이 말은 곧 한 행에서 로봇은 오른쪽으로만 이동하거나, 왼쪽으로만 이동할 수 있다는 것과 같다.

이제 이렇게 세운 계획을 통해 구체적인 해결 방법을 구상해 보자.

 

■ 1행의 경우

dp의 끝 인덱스 0은 해당 값이 실제로 그 칸까지 도달하는 데의 최대 가치임을 의미한다.

 

■ 1행 이후의 경우

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define MINF -99999999
 
using namespace std;
typedef pair<int, int> p;
 
int board[1001][1001];
int dp[1001][1001][3];
int n, m;
 
void get_dp() {
    for (int row = 2; row <= n; row++) {
        //좌 -> 우로 가는 최대가치 갱신
        dp[row][1][1] = dp[row - 1][1][0] + board[row][1];
        for (int col = 2; col <= m; col++) {
            int dpval = max(dp[row - 1][col][0], dp[row][col - 1][1]) + board[row][col];
            dp[row][col][1] = max(dp[row][col][1], dpval);
        }
 
        //우 -> 좌로 가는 최대가치 갱신
        dp[row][m][2] = dp[row - 1][m][0] + board[row][m];
        for (int col = m - 1; col >= 1; col--) {
            int dpval = max(dp[row - 1][col][0], dp[row][col + 1][2]) + board[row][col];
            dp[row][col][2] = max(dp[row][col][2], dpval);
        }
 
        //최종 dp값 결정
        for (int col = 1; col <= m; col++)
            dp[row][col][0] = max(dp[row][col][1], dp[row][col][2]);
    }
}
 
void init() {
    cin >> n >> m;
 
    for(int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> board[i][j];
            for (int k = 0; k < 3; k++) dp[i][j][k] = MINF;
        }
 
    int sum = 0; 
    for (int i = 1; i <= m; i++) {
        for (int k = 0; k < 3; k++) dp[1][i][k] = sum + board[1][i];
        sum += board[1][i];
    }
 
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    get_dp();
 
    printf("%d\n", dp[n][m][0]);
 
    return 0;
}