BOJ 2169 로봇 조종하기

2169번: 로봇 조종하기 (acmicpc.net)

2169번: 로봇 조종하기

 

선 요약 : DP문제였다.

 

처음에는 다음 조건들 때문에 완전 탐색으로 풀어야하나 고민했었다.

1. 탐사한 지역은 다시 탐사하지 않는다.

2. 로봇은 배열에서 오른쪽, 왼쪽, 아래쪽으로 이동하지만, 위쪽으로 이동할 수 없다.  (내가 지금까지 봤었던 DP문제들은 전부 한쪽 방향으로만 움직이면서 풀었기 때문에 왼쪽, 오른쪽 두방향으로 움직이는 이 조건 때문에 처음에는 DP라고 생각하지 못했다.)

 

하지만, 시간복잡도가 너무 커서 불가능하다고 생각했고, 문제를 잘 읽어보면서 시간을 줄일 수 있는 방안을 고민하였다.

그중 "위쪽 방향으로 이동할 수 없다" 는 조건 생각하면서 문제에 접근하였다.

첫째, arr[i][j] 로 접근 할 수 있는 i-1행의 칸은 arr[i-1][j]가 유일하다.

둘째, 이는 arr[i][j] 와 좌우로 인접해있는 arr[i][j-1], arr[i][j+1]도 마찬가지다.

셋째, 그렇다면, i-1행까지 값이 구해져있다면, arr[i][j] 까지 탐사하는데 드는 비용은 arr[i-1][j] + map[i][j] 이다

넷째, 탐사한 지역은 다시 탐사하지 않으니, 왼쪽에서 오른쪽으로 탐사하는 경우, 오른쪽에서 왼쪽으로 탐사하는 경우를 각각 구해서 이중 최대값을 선택하자. 이와중에 위에서 내려오는 경우가 최대라면 이를 반영하여 탐사를 진행한다. (처음 구현할 땐. 각각 구하지 않고 한쪽 방향으로 탐사했던 결과를 반대편 방향으로 탐사할때도 써서 문제가 되었다... ㅠ)

다섯째, 그러면 이문제는 DP겠네!

위와 같은 생각으로 만들어진 점화식은 다음과 같이 된다

왼쪽 -> 오른쪽 : arr[j][1] = max ( DP[i-1][j] , arr[j-1][1] ) + map[i][j] ( 2 <= j <= m)

오른쪽 -> 왼쪽 : arr[j][2] = max ( DP[i-1][j] , arr[j+1][2] ) + map[i][j] ( 1 <= j < m )

DP[i][j] = max(arr[j][1], arr[j][2])

 

아래는 코드이다.

#include <cstdio>

int n,m;
int map[1001][1001];
int total_value[1001][1001];

int my_max(const int a, const int b){
  return a > b ? a : b;
}

int main(){

  scanf("%d%d",&n,&m);

  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      scanf("%d",&(map[i][j]));
    }
  }

  for(int i=1;i<=m;i++){
    total_value[1][i] = total_value[1][i-1] + map[1][i];
  }
  
  int arr[1001][3]={0,};
  for(int i=2;i<=n;i++){

    arr[1][1] = total_value[i-1][1] + map[i][1];
    for(int j=2;j<=m;j++){
      arr[j][1] = my_max(total_value[i-1][j], arr[j-1][1]) + map[i][j];
    }
    arr[m][2] = total_value[i-1][m] + map[i][m];
    for(int j=m-1;j>=1;j--){
      arr[j][2] = my_max(total_value[i-1][j], arr[j+1][2]) + map[i][j];
    }
    for(int j=1;j<=m;j++){
      total_value[i][j] = my_max(arr[j][1], arr[j][2]);
    }
  }


  printf("%d\n",total_value[n][m]);

  return 0;
}

 

PS. arr[1][1], arr[m][2] 초기화를 하지 못하여 이전 행의 값이 반영되는 문제 때문에 틀렸습니다가 계속 떳다...  DP에서는 초기화를 잘 하도록 하자