(2169) 로봇 조종하기

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

단계별로 풀어보기

50단계(동적 계획법 4) 2번째

 

 

 

한 번 지난 지역을 다시 지날 수 없으므로 같은 행에서 왼쪽으로 갔다면 계속 왼쪽, 오른쪽으로 갔다면 계속 오른쪽으로 가야 한다.

따라서 DP배열을 만들 때 현재 좌표 뿐만 아니라 왼쪽, 오른쪽 이동 여부까지 저장해야 한다.

오른쪽으로 이동하는 DP에서 오른쪽으로 가며 DP를 갱신하고, 왼쪽으로 이동하는 DP에서 왼쪽으로 가며 DP를 갱신한다. 이후 양쪽 방향 중 큰 값으로 아래쪽으로 이동하는 DP를 갱신하면 된다. 이때 아래쪽으로 가면 왼쪽, 오른쪽 전부 가능하므로 둘 다 값을 넣어준다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 100000001

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector v(n+2, vector<int> (m+2));
  vector dp(2, vector<vector<int>> (n+2, vector<int> (m+2, -INF)));
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin >> v[i][j];
    }
  }
  
  dp[0][1][1]= v[1][1];
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      dp[0][i][j+1]= max(dp[0][i][j+1], dp[0][i][j]+v[i][j+1]);
    }
    for(int j=m;j>=1;j--){
      dp[1][i][j-1]= max(dp[1][i][j-1], dp[1][i][j]+v[i][j-1]);
      dp[0][i+1][j]= max(dp[0][i+1][j], max(dp[0][i][j], dp[1][i][j])+v[i+1][j]);
      dp[1][i+1][j]= max(dp[1][i+1][j], max(dp[0][i][j], dp[1][i][j])+v[i+1][j]);
    }
  }
  
  cout << max(dp[0][n][m], dp[1][n][m]);
  
  return 0;
}