[백준] 2169: 로봇 조종하기

0. 문제 주소

 

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

2169번: 로봇 조종하기

 

 

1. 풀이

 

이게 왜 골드 1이지???

 

기존 문제들과 달랐던 점은 다음과 같다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다.

 

 

dp 배열은 3차원으로 짰는데,

dp[i][j][0] = (i, j) 기준 위쪽, 왼쪽에서 (i, j)로 올 때 가장 큰 값을 저장
dp[i][j][1] = (i, j) 기준 위쪽, 오른쪽에서 (i, j)로 올 때 가장 큰 값을 저장

이때 주의할 점은 왼쪽, 오른쪽에서 올 때 어떤 값을 가져올 것이냐다.

 

dp[i][j][0]을 예시로 들어보자. 위쪽에서부터 가져올 수 있는 값은 dp[i-1][j][0], dp[i-1][j][1]이다. 바로 위에 있는 칸은 그 전이 왼쪽에서 왔던, 오른쪽에서 왔던 둘 중에 큰 값만 취하면 되기 때문이다.

 

하지만 왼쪽에서 가져올 수 있는 값은 dp[i][j-1][0] 뿐이다.

dp[i][j-1][1]이 의미하는 것은 (i, j-1) 기준 오른쪽 칸을 거쳐 (i, j-1)로 왔을 때의 최댓값인데, 밑줄 친 칸이 바로 (i, j)이기 때문이다. 그렇기 때문에 dp[i][j][0]은 다음과 같이 초기화해야 한다.

 

dp[i][j][0] = grid[i][j] + max(max(dp[i-1][j][0], dp[i-1][j][1]), dp[i][j-1][0]);

 

그 밖에 처음 시작하는 칸이 (1, 1)이기 때문에 첫줄은 무조건 왼쪽으로만 이동해야 한다는 점, index 가장자리 처리 등이 주의해야 할 점이었다.

 

 

그리고

배열의 각 수는 절댓값이 100을 넘지 않는 정수이다.

라는 조건 때문에 dp 배열을 전부 -1000으로 초기화했는데, WA가 떠서 당황했었다.

생각해 본 결과 1 <= N, M <= 1000 이니까 전부 다 -100이면 최댓값 비교해서 문제가 생기는 반례가 있었다.

그래서 MIN = 2e-9로 초기화하니까 AC를 받을 수 있었다.

 

2. 풀이 코드

 

* 유의할 점

1. 첫 줄은 dp[1][j][0]만 초기화 (왼쪽으로만 이동 가능)

2. dp 배열 초기화 : MIN 값 안전하게

 

#include <bits/stdc++.h>
#define MAX 1005
#define MIN -2e9

using namespace std;

int N, M;
int grid[MAX][MAX];
int dp[MAX][MAX][2];


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d %d", &N, &M);
    for (int i=0;i<=N+1;i++){
        for (int j=0;j<=M+1;j++){
            dp[i][j][0] = dp[i][j][1] = MIN;
        }
    }
    for (int i=1;i<=N;i++){
        for (int j=1;j<=M;j++){
            scanf("%d", &grid[i][j]);
        }
    }

    dp[1][1][0] = grid[1][1];
    for (int j=2;j<=M;j++){
        dp[1][j][0]= grid[1][j] + dp[1][j-1][0];
    }

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

    printf("%d\n", max(dp[N][M][0], dp[N][M][1]));
}