BOJ 6704 - Tourist

BOJ 6704 - Tourist

$dp[y_1][x_1][y_2]=$ 각 위치가 $(y_1,x_1), (y_2,x_2)$ 에 있을 때 최대 점수라고 하자.

$x_2=y_1+x_1-y_2$ 로 두고 차원을 줄여줄 수 있다.

갔다가 다시 오는걸로 말고 한 번에 두 개로 가는것을 생각하면 된다.

왜냐면 $(y_1,x_1)$ 이 이전에 방문한 지점을 $(y_2,x_2)$가 이후에 방문할 일이 문제의 조건상 없기 때문이다.

따라서 $O(4N^2M)$ 으로 DP를 돌려줄 수 있다.

const int dy[] = {0, 1}, dx[] = {1, 0};  
void solve() {  
   int Y, X;  
   cin >> X >> Y;  
   vs b(Y);  
   fv(b);  
   vector<vvi> dp(Y, vvi(X, vi(Y, -1e9)));  
   dp[0][0][0] = b[0][0] == '*' ? 1 : 0;  
   queue<array<int, 3>> q;  
   q.push({0, 0, 0});  
   while (sz(q)) {  
      auto [y1, x1, y2] = q.front();  
      q.pop();  
      int x2 = y1 + x1 - y2;  
      for (int d1 = 0; d1 < 2; d1++) {  
         for (int d2 = 0; d2 < 2; d2++) {  
            int ny1 = y1 + dy[d1], nx1 = x1 + dx[d1];  
            int ny2 = y2 + dy[d2], nx2 = x2 + dx[d2];  
            if (ny1 >= 0 && ny1 < Y && nx1 >= 0 && nx1 < X &&  
               ny2 >= 0 && ny2 < Y && nx2 >= 0 && nx2 < X && b[ny1][nx1] != '#' && b[ny2][nx2] != '#') {  
               int cost_add = (b[ny1][nx1] == '*') + (b[ny2][nx2] == '*');  
               if (b[ny1][nx1] == '*' && mp(ny1, nx1) == mp(ny2, nx2)) cost_add--;  
               if (dp[ny1][nx1][ny2] < cost_add + dp[y1][x1][y2]) {  
                  dp[ny1][nx1][ny2] = cost_add + dp[y1][x1][y2];  
                  q.push({ny1, nx1, ny2});  
               }  
            }  
         }  
      }  
   }  
   cout << dp[Y - 1][X - 1][Y - 1] << endl;  
}