로봇 조종하기

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

대충보면 아주 간단한 DP로 풀 수 있는 최적화 문제이나, 조금 찬찬히 뜯어보면 점화식을 세우기가 조금 까다롭다.

기본적으로 로봇이동이 좌/우/하 세 방향으로 가능하기 때문에 현재 문제에 미래의 문제가 의존하고, 미래의 문제가 현재의 문제에 의존한다.

문제를 조금 더 유심히 관찰해보면 다행히도 이를 해결해줄 수 있는데, 로봇이 방문한 곳은 다시 방문하지 않는다는 점을 떠올리자.

cache를 아래와 같이 정의해준다면 현재/미래 상호 의존 관계를 잘 해결해 줄 수 있다.

• cache[r][c][d]: (r, c) 위치에 로봇이 d(좌/우/상) 방향에서 진입해 들어올 때, 최적해

위의 정의로부터 의존관계는 아래와 같이 정해질 수 있다.

• cache[r][c][상]: cache[r-1][c][좌], cache[r-1][c][우], cache[r-1][c][상]에 의존
• cache[r][c][좌]: cache[r][c-1][좌], cache[r][c-1][상]에 의존
• cache[r][c][우]: cache[r][c+1][우], cache[r][c+1][상]에 의존

따라서, 행 순서로 문제를 풀어주되 좌->우로 한번 / 우->좌로 한번씩 풀어주면 된다.

#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

const int kMaxN = 1000;
const int kMaxM = 1000;

const int kL = 0;
const int kR = 1;
const int kU = 2;

const int kImpossible = -101 * kMaxN * kMaxM;

int n, m;
int mars[kMaxN][kMaxM];
int cache[kMaxN][kMaxM][3];

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> n >> m;

  for (int r = 0; r < n; ++r)
  {
    for (int c = 0; c < m; ++c)
    {
      cin >> mars[r][c];
    }
  }

  // Initialize
  for (int r = 0; r < n; ++r)
  {
    for (int c = 0; c < m; ++c)
    {
      cache[r][c][kL] = kImpossible;
      cache[r][c][kR] = kImpossible;
      cache[r][c][kU] = kImpossible;
    }
  }

  // Solve
  int sum = 0;
  for (int c = 0; c < m; ++c)
  {
    cache[0][c][kL] = sum + mars[0][c];
    sum += mars[0][c];
  }

  for (int r = 1; r < n; ++r)
  {
    for (int c = 0; c < m; ++c)
    {
      if (cache[r - 1][c][kL] != kImpossible)
      {
        cache[r][c][kU] = max(cache[r][c][kU], cache[r - 1][c][kL] + mars[r][c]);
      }
      if (cache[r - 1][c][kR] != kImpossible)
      {
        cache[r][c][kU] = max(cache[r][c][kU], cache[r - 1][c][kR] + mars[r][c]);
      }
      if (cache[r - 1][c][kU] != kImpossible)
      {
        cache[r][c][kU] = max(cache[r][c][kU], cache[r - 1][c][kU] + mars[r][c]);
      }
    }

    for (int c = 1; c < m; ++c)
    {
      if (cache[r][c - 1][kL] != kImpossible)
      {
        cache[r][c][kL] = max(cache[r][c][kL], cache[r][c - 1][kL] + mars[r][c]);
      }

      if (cache[r][c - 1][kU] != kImpossible)
      {
        cache[r][c][kL] = max(cache[r][c][kL], cache[r][c - 1][kU] + mars[r][c]);
      }
    }

    for (int c = m - 2; c >= 0; --c)
    {
      if (cache[r][c + 1][kR] != kImpossible)
      {
        cache[r][c][kR] = max(cache[r][c][kR], cache[r][c + 1][kR] + mars[r][c]);
      }

      if (cache[r][c + 1][kU] != kImpossible)
      {
        cache[r][c][kR] = max(cache[r][c][kR], cache[r][c + 1][kU] + mars[r][c]);
      }
    }
  }

  cout << max(cache[n - 1][m - 1][kL], max(cache[n - 1][m - 1][kR], cache[n - 1][m - 1][kU])) << '\n';

  return 0;
}